
  /*
  ** SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) 
  ** Copyright (C) [dates of first publication] Silicon Graphics, Inc.
  ** All Rights Reserved.
  **
  ** Permission is hereby granted, free of charge, to any person obtaining a copy
  ** of this software and associated documentation files (the "Software"), to deal
  ** in the Software without restriction, including without limitation the rights
  ** to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
  ** of the Software, and to permit persons to whom the Software is furnished to do so,
  ** subject to the following conditions:
  ** 
  ** The above copyright notice including the dates of first publication and either this
  ** permission notice or a reference to http://oss.sgi.com/projects/FreeB/ shall be
  ** included in all copies or substantial portions of the Software. 
  **
  ** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
  ** INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
  ** PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL SILICON GRAPHICS, INC.
  ** BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  ** TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE
  ** OR OTHER DEALINGS IN THE SOFTWARE.
  ** 
  ** Except as contained in this notice, the name of Silicon Graphics, Inc. shall not
  ** be used in advertising or otherwise to promote the sale, use or other dealings in
  ** this Software without prior written authorization from Silicon Graphics, Inc.
  */
  /*
  ** Author: Mikko Mononen, Aug 2013.
  ** The code is based on GLU libtess by Eric Veach, July 1994
  */
  
    "use strict";
  
    /* Public API */
  
    var Tess2 = {};
  
    export default Tess2
    
    Tess2.WINDING_ODD = 0;
    Tess2.WINDING_NONZERO = 1;
    Tess2.WINDING_POSITIVE = 2;
    Tess2.WINDING_NEGATIVE = 3;
    Tess2.WINDING_ABS_GEQ_TWO = 4;
  
    Tess2.POLYGONS = 0;
    Tess2.CONNECTED_POLYGONS = 1;
    Tess2.BOUNDARY_CONTOURS = 2;
  
    Tess2.tesselate = function(opts) {
      var debug =  opts.debug || false;
      var tess = new Tesselator();
      for (var i = 0; i < opts.contours.length; i++) {
        tess.addContour(opts.vertexSize || 2, opts.contours[i]);
      }
      tess.tesselate(opts.windingRule || Tess2.WINDING_ODD,
               opts.elementType || Tess2.POLYGONS,
               opts.polySize || 3,
               opts.vertexSize || 2,
               opts.normal || [0,0,1]);
      return {
        vertices: tess.vertices,
        vertexIndices: tess.vertexIndices,
        vertexCount: tess.vertexCount,
        elements: tess.elements,
        elementCount: tess.elementCount,
        mesh: debug ? tess.mesh : undefined
      };
    };
  
    /* Internal */
  
    var assert = function(cond) {
      if (!cond) {
        throw "Assertion Failed!";
      }
    }
  
    /* The mesh structure is similar in spirit, notation, and operations
    * to the "quad-edge" structure (see L. Guibas and J. Stolfi, Primitives
    * for the manipulation of general subdivisions and the computation of
    * Voronoi diagrams, ACM Transactions on Graphics, 4(2):74-123, April 1985).
    * For a simplified description, see the course notes for CS348a,
    * "Mathematical Foundations of Computer Graphics", available at the
    * Stanford bookstore (and taught during the fall quarter).
    * The implementation also borrows a tiny subset of the graph-based approach
    * use in Mantyla's Geometric Work Bench (see M. Mantyla, An Introduction
    * to Sold Modeling, Computer Science Press, Rockville, Maryland, 1988).
    *
    * The fundamental data structure is the "half-edge".  Two half-edges
    * go together to make an edge, but they point in opposite directions.
    * Each half-edge has a pointer to its mate (the "symmetric" half-edge Sym),
    * its origin vertex (Org), the face on its left side (Lface), and the
    * adjacent half-edges in the CCW direction around the origin vertex
    * (Onext) and around the left face (Lnext).  There is also a "next"
    * pointer for the global edge list (see below).
    *
    * The notation used for mesh navigation:
    *  Sym   = the mate of a half-edge (same edge, but opposite direction)
    *  Onext = edge CCW around origin vertex (keep same origin)
    *  Dnext = edge CCW around destination vertex (keep same dest)
    *  Lnext = edge CCW around left face (dest becomes new origin)
    *  Rnext = edge CCW around right face (origin becomes new dest)
    *
    * "prev" means to substitute CW for CCW in the definitions above.
    *
    * The mesh keeps global lists of all vertices, faces, and edges,
    * stored as doubly-linked circular lists with a dummy header node.
    * The mesh stores pointers to these dummy headers (vHead, fHead, eHead).
    *
    * The circular edge list is special; since half-edges always occur
    * in pairs (e and e->Sym), each half-edge stores a pointer in only
    * one direction.  Starting at eHead and following the e->next pointers
    * will visit each *edge* once (ie. e or e->Sym, but not both).
    * e->Sym stores a pointer in the opposite direction, thus it is
    * always true that e->Sym->next->Sym->next == e.
    *
    * Each vertex has a pointer to next and previous vertices in the
    * circular list, and a pointer to a half-edge with this vertex as
    * the origin (NULL if this is the dummy header).  There is also a
    * field "data" for client data.
    *
    * Each face has a pointer to the next and previous faces in the
    * circular list, and a pointer to a half-edge with this face as
    * the left face (NULL if this is the dummy header).  There is also
    * a field "data" for client data.
    *
    * Note that what we call a "face" is really a loop; faces may consist
    * of more than one loop (ie. not simply connected), but there is no
    * record of this in the data structure.  The mesh may consist of
    * several disconnected regions, so it may not be possible to visit
    * the entire mesh by starting at a half-edge and traversing the edge
    * structure.
    *
    * The mesh does NOT support isolated vertices; a vertex is deleted along
    * with its last edge.  Similarly when two faces are merged, one of the
    * faces is deleted (see tessMeshDelete below).  For mesh operations,
    * all face (loop) and vertex pointers must not be NULL.  However, once
    * mesh manipulation is finished, TESSmeshZapFace can be used to delete
    * faces of the mesh, one at a time.  All external faces can be "zapped"
    * before the mesh is returned to the client; then a NULL face indicates
    * a region which is not part of the output polygon.
    */
  
    function TESSvertex() {
      this.next = null;	/* next vertex (never NULL) */
      this.prev = null;	/* previous vertex (never NULL) */
      this.anEdge = null;	/* a half-edge with this origin */
  
      /* Internal data (keep hidden) */
      this.coords = [0,0,0];	/* vertex location in 3D */
      this.s = 0.0;
      this.t = 0.0;			/* projection onto the sweep plane */
      this.pqHandle = 0;		/* to allow deletion from priority queue */
      this.n = 0;				/* to allow identify unique vertices */
      this.idx = 0;			/* to allow map result to original verts */
    } 
  
    function TESSface() {
      this.next = null;		/* next face (never NULL) */
      this.prev = null;		/* previous face (never NULL) */
      this.anEdge = null;		/* a half edge with this left face */
  
      /* Internal data (keep hidden) */
      this.trail = null;		/* "stack" for conversion to strips */
      this.n = 0;				/* to allow identiy unique faces */
      this.marked = false;	/* flag for conversion to strips */
      this.inside = false;	/* this face is in the polygon interior */
    };
  
    function TESShalfEdge(side) {
      this.next = null;		/* doubly-linked list (prev==Sym->next) */
      this.Sym = null;		/* same edge, opposite direction */
      this.Onext = null;		/* next edge CCW around origin */
      this.Lnext = null;		/* next edge CCW around left face */
      this.Org = null;		/* origin vertex (Overtex too long) */
      this.Lface = null;		/* left face */
  
      /* Internal data (keep hidden) */
      this.activeRegion = null;	/* a region with this upper edge (sweep.c) */
      this.winding = 0;			/* change in winding number when crossing
                       from the right face to the left face */
      this.side = side;
    };
  
    TESShalfEdge.prototype = {
      get Rface() { return this.Sym.Lface; },
      set Rface(v) { this.Sym.Lface = v; },
      get Dst() { return this.Sym.Org; },
      set Dst(v) { this.Sym.Org = v; },
      get Oprev() { return this.Sym.Lnext; },
      set Oprev(v) { this.Sym.Lnext = v; },
      get Lprev() { return this.Onext.Sym; },
      set Lprev(v) { this.Onext.Sym = v; },
      get Dprev() { return this.Lnext.Sym; },
      set Dprev(v) { this.Lnext.Sym = v; },
      get Rprev() { return this.Sym.Onext; },
      set Rprev(v) { this.Sym.Onext = v; },
      get Dnext() { return /*this.Rprev*/this.Sym.Onext.Sym; },  /* 3 pointers */
      set Dnext(v) { /*this.Rprev*/this.Sym.Onext.Sym = v; },  /* 3 pointers */
      get Rnext() { return /*this.Oprev*/this.Sym.Lnext.Sym; },  /* 3 pointers */
      set Rnext(v) { /*this.Oprev*/this.Sym.Lnext.Sym = v; },  /* 3 pointers */
    };
  
  
  
    function TESSmesh() {
      var v = new TESSvertex();
      var f = new TESSface();
      var e = new TESShalfEdge(0);
      var eSym = new TESShalfEdge(1);
  
      v.next = v.prev = v;
      v.anEdge = null;
  
      f.next = f.prev = f;
      f.anEdge = null;
      f.trail = null;
      f.marked = false;
      f.inside = false;
  
      e.next = e;
      e.Sym = eSym;
      e.Onext = null;
      e.Lnext = null;
      e.Org = null;
      e.Lface = null;
      e.winding = 0;
      e.activeRegion = null;
  
      eSym.next = eSym;
      eSym.Sym = e;
      eSym.Onext = null;
      eSym.Lnext = null;
      eSym.Org = null;
      eSym.Lface = null;
      eSym.winding = 0;
      eSym.activeRegion = null;
  
      this.vHead = v;		/* dummy header for vertex list */
      this.fHead = f;		/* dummy header for face list */
      this.eHead = e;		/* dummy header for edge list */
      this.eHeadSym = eSym;	/* and its symmetric counterpart */
    };
  
    /* The mesh operations below have three motivations: completeness,
    * convenience, and efficiency.  The basic mesh operations are MakeEdge,
    * Splice, and Delete.  All the other edge operations can be implemented
    * in terms of these.  The other operations are provided for convenience
    * and/or efficiency.
    *
    * When a face is split or a vertex is added, they are inserted into the
    * global list *before* the existing vertex or face (ie. e->Org or e->Lface).
    * This makes it easier to process all vertices or faces in the global lists
    * without worrying about processing the same data twice.  As a convenience,
    * when a face is split, the "inside" flag is copied from the old face.
    * Other internal data (v->data, v->activeRegion, f->data, f->marked,
    * f->trail, e->winding) is set to zero.
    *
    * ********************** Basic Edge Operations **************************
    *
    * tessMeshMakeEdge( mesh ) creates one edge, two vertices, and a loop.
    * The loop (face) consists of the two new half-edges.
    *
    * tessMeshSplice( eOrg, eDst ) is the basic operation for changing the
    * mesh connectivity and topology.  It changes the mesh so that
    *  eOrg->Onext <- OLD( eDst->Onext )
    *  eDst->Onext <- OLD( eOrg->Onext )
    * where OLD(...) means the value before the meshSplice operation.
    *
    * This can have two effects on the vertex structure:
    *  - if eOrg->Org != eDst->Org, the two vertices are merged together
    *  - if eOrg->Org == eDst->Org, the origin is split into two vertices
    * In both cases, eDst->Org is changed and eOrg->Org is untouched.
    *
    * Similarly (and independently) for the face structure,
    *  - if eOrg->Lface == eDst->Lface, one loop is split into two
    *  - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one
    * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected.
    *
    * tessMeshDelete( eDel ) removes the edge eDel.  There are several cases:
    * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop
    * eDel->Lface is deleted.  Otherwise, we are splitting one loop into two;
    * the newly created loop will contain eDel->Dst.  If the deletion of eDel
    * would create isolated vertices, those are deleted as well.
    *
    * ********************** Other Edge Operations **************************
    *
    * tessMeshAddEdgeVertex( eOrg ) creates a new edge eNew such that
    * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex.
    * eOrg and eNew will have the same left face.
    *
    * tessMeshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew,
    * such that eNew == eOrg->Lnext.  The new vertex is eOrg->Dst == eNew->Org.
    * eOrg and eNew will have the same left face.
    *
    * tessMeshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst
    * to eDst->Org, and returns the corresponding half-edge eNew.
    * If eOrg->Lface == eDst->Lface, this splits one loop into two,
    * and the newly created loop is eNew->Lface.  Otherwise, two disjoint
    * loops are merged into one, and the loop eDst->Lface is destroyed.
    *
    * ************************ Other Operations *****************************
    *
    * tessMeshNewMesh() creates a new mesh with no edges, no vertices,
    * and no loops (what we usually call a "face").
    *
    * tessMeshUnion( mesh1, mesh2 ) forms the union of all structures in
    * both meshes, and returns the new mesh (the old meshes are destroyed).
    *
    * tessMeshDeleteMesh( mesh ) will free all storage for any valid mesh.
    *
    * tessMeshZapFace( fZap ) destroys a face and removes it from the
    * global face list.  All edges of fZap will have a NULL pointer as their
    * left face.  Any edges which also have a NULL pointer as their right face
    * are deleted entirely (along with any isolated vertices this produces).
    * An entire mesh can be deleted by zapping its faces, one at a time,
    * in any order.  Zapped faces cannot be used in further mesh operations!
    *
    * tessMeshCheckMesh( mesh ) checks a mesh for self-consistency.
    */
  
    TESSmesh.prototype = {
  
      /* MakeEdge creates a new pair of half-edges which form their own loop.
      * No vertex or face structures are allocated, but these must be assigned
      * before the current edge operation is completed.
      */
      //static TESShalfEdge *MakeEdge( TESSmesh* mesh, TESShalfEdge *eNext )
      makeEdge_: function(eNext) {
        var e = new TESShalfEdge(0);
        var eSym = new TESShalfEdge(1);
  
        /* Make sure eNext points to the first edge of the edge pair */
        if( eNext.Sym.side < eNext.side ) { eNext = eNext.Sym; }
  
        /* Insert in circular doubly-linked list before eNext.
        * Note that the prev pointer is stored in Sym->next.
        */
        var ePrev = eNext.Sym.next;
        eSym.next = ePrev;
        ePrev.Sym.next = e;
        e.next = eNext;
        eNext.Sym.next = eSym;
  
        e.Sym = eSym;
        e.Onext = e;
        e.Lnext = eSym;
        e.Org = null;
        e.Lface = null;
        e.winding = 0;
        e.activeRegion = null;
  
        eSym.Sym = e;
        eSym.Onext = eSym;
        eSym.Lnext = e;
        eSym.Org = null;
        eSym.Lface = null;
        eSym.winding = 0;
        eSym.activeRegion = null;
  
        return e;
      },
  
      /* Splice( a, b ) is best described by the Guibas/Stolfi paper or the
      * CS348a notes (see mesh.h).  Basically it modifies the mesh so that
      * a->Onext and b->Onext are exchanged.  This can have various effects
      * depending on whether a and b belong to different face or vertex rings.
      * For more explanation see tessMeshSplice() below.
      */
      // static void Splice( TESShalfEdge *a, TESShalfEdge *b )
      splice_: function(a, b) {
        var aOnext = a.Onext;
        var bOnext = b.Onext;
        aOnext.Sym.Lnext = b;
        bOnext.Sym.Lnext = a;
        a.Onext = bOnext;
        b.Onext = aOnext;
      },
  
      /* MakeVertex( newVertex, eOrig, vNext ) attaches a new vertex and makes it the
      * origin of all edges in the vertex loop to which eOrig belongs. "vNext" gives
      * a place to insert the new vertex in the global vertex list.  We insert
      * the new vertex *before* vNext so that algorithms which walk the vertex
      * list will not see the newly created vertices.
      */
      //static void MakeVertex( TESSvertex *newVertex, TESShalfEdge *eOrig, TESSvertex *vNext )
      makeVertex_: function(newVertex, eOrig, vNext) {
        var vNew = newVertex;
        assert(vNew !== null);
  
        /* insert in circular doubly-linked list before vNext */
        var vPrev = vNext.prev;
        vNew.prev = vPrev;
        vPrev.next = vNew;
        vNew.next = vNext;
        vNext.prev = vNew;
  
        vNew.anEdge = eOrig;
        /* leave coords, s, t undefined */
  
        /* fix other edges on this vertex loop */
        var e = eOrig;
        do {
          e.Org = vNew;
          e = e.Onext;
        } while(e !== eOrig);
      },
  
      /* MakeFace( newFace, eOrig, fNext ) attaches a new face and makes it the left
      * face of all edges in the face loop to which eOrig belongs.  "fNext" gives
      * a place to insert the new face in the global face list.  We insert
      * the new face *before* fNext so that algorithms which walk the face
      * list will not see the newly created faces.
      */
      // static void MakeFace( TESSface *newFace, TESShalfEdge *eOrig, TESSface *fNext )
      makeFace_: function(newFace, eOrig, fNext) {
        var fNew = newFace;
        assert(fNew !== null); 
  
        /* insert in circular doubly-linked list before fNext */
        var fPrev = fNext.prev;
        fNew.prev = fPrev;
        fPrev.next = fNew;
        fNew.next = fNext;
        fNext.prev = fNew;
  
        fNew.anEdge = eOrig;
        fNew.trail = null;
        fNew.marked = false;
  
        /* The new face is marked "inside" if the old one was.  This is a
        * convenience for the common case where a face has been split in two.
        */
        fNew.inside = fNext.inside;
  
        /* fix other edges on this face loop */
        var e = eOrig;
        do {
          e.Lface = fNew;
          e = e.Lnext;
        } while(e !== eOrig);
      },
  
      /* KillEdge( eDel ) destroys an edge (the half-edges eDel and eDel->Sym),
      * and removes from the global edge list.
      */
      //static void KillEdge( TESSmesh *mesh, TESShalfEdge *eDel )
      killEdge_: function(eDel) {
        /* Half-edges are allocated in pairs, see EdgePair above */
        if( eDel.Sym.side < eDel.side ) { eDel = eDel.Sym; }
  
        /* delete from circular doubly-linked list */
        var eNext = eDel.next;
        var ePrev = eDel.Sym.next;
        eNext.Sym.next = ePrev;
        ePrev.Sym.next = eNext;
      },
  
  
      /* KillVertex( vDel ) destroys a vertex and removes it from the global
      * vertex list.  It updates the vertex loop to point to a given new vertex.
      */
      //static void KillVertex( TESSmesh *mesh, TESSvertex *vDel, TESSvertex *newOrg )
      killVertex_: function(vDel, newOrg) {
        var eStart = vDel.anEdge;
        /* change the origin of all affected edges */
        var e = eStart;
        do {
          e.Org = newOrg;
          e = e.Onext;
        } while(e !== eStart);
  
        /* delete from circular doubly-linked list */
        var vPrev = vDel.prev;
        var vNext = vDel.next;
        vNext.prev = vPrev;
        vPrev.next = vNext;
      },
  
      /* KillFace( fDel ) destroys a face and removes it from the global face
      * list.  It updates the face loop to point to a given new face.
      */
      //static void KillFace( TESSmesh *mesh, TESSface *fDel, TESSface *newLface )
      killFace_: function(fDel, newLface) {
        var eStart = fDel.anEdge;
  
        /* change the left face of all affected edges */
        var e = eStart;
        do {
          e.Lface = newLface;
          e = e.Lnext;
        } while(e !== eStart);
  
        /* delete from circular doubly-linked list */
        var fPrev = fDel.prev;
        var fNext = fDel.next;
        fNext.prev = fPrev;
        fPrev.next = fNext;
      },
  
      /****************** Basic Edge Operations **********************/
  
      /* tessMeshMakeEdge creates one edge, two vertices, and a loop (face).
      * The loop consists of the two new half-edges.
      */
      //TESShalfEdge *tessMeshMakeEdge( TESSmesh *mesh )
      makeEdge: function() {
        var newVertex1 = new TESSvertex();
        var newVertex2 = new TESSvertex();
        var newFace = new TESSface();
        var e = this.makeEdge_( this.eHead);
        this.makeVertex_( newVertex1, e, this.vHead );
        this.makeVertex_( newVertex2, e.Sym, this.vHead );
        this.makeFace_( newFace, e, this.fHead );
        return e;
      },
  
      /* tessMeshSplice( eOrg, eDst ) is the basic operation for changing the
      * mesh connectivity and topology.  It changes the mesh so that
      *	eOrg->Onext <- OLD( eDst->Onext )
      *	eDst->Onext <- OLD( eOrg->Onext )
      * where OLD(...) means the value before the meshSplice operation.
      *
      * This can have two effects on the vertex structure:
      *  - if eOrg->Org != eDst->Org, the two vertices are merged together
      *  - if eOrg->Org == eDst->Org, the origin is split into two vertices
      * In both cases, eDst->Org is changed and eOrg->Org is untouched.
      *
      * Similarly (and independently) for the face structure,
      *  - if eOrg->Lface == eDst->Lface, one loop is split into two
      *  - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one
      * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected.
      *
      * Some special cases:
      * If eDst == eOrg, the operation has no effect.
      * If eDst == eOrg->Lnext, the new face will have a single edge.
      * If eDst == eOrg->Lprev, the old face will have a single edge.
      * If eDst == eOrg->Onext, the new vertex will have a single edge.
      * If eDst == eOrg->Oprev, the old vertex will have a single edge.
      */
      //int tessMeshSplice( TESSmesh* mesh, TESShalfEdge *eOrg, TESShalfEdge *eDst )
      splice: function(eOrg, eDst) {
        var joiningLoops = false;
        var joiningVertices = false;
  
        if( eOrg === eDst ) return;
  
        if( eDst.Org !== eOrg.Org ) {
          /* We are merging two disjoint vertices -- destroy eDst->Org */
          joiningVertices = true;
          this.killVertex_( eDst.Org, eOrg.Org );
        }
        if( eDst.Lface !== eOrg.Lface ) {
          /* We are connecting two disjoint loops -- destroy eDst->Lface */
          joiningLoops = true;
          this.killFace_( eDst.Lface, eOrg.Lface );
        }
  
        /* Change the edge structure */
        this.splice_( eDst, eOrg );
  
        if( ! joiningVertices ) {
          var newVertex = new TESSvertex();
  
          /* We split one vertex into two -- the new vertex is eDst->Org.
          * Make sure the old vertex points to a valid half-edge.
          */
          this.makeVertex_( newVertex, eDst, eOrg.Org );
          eOrg.Org.anEdge = eOrg;
        }
        if( ! joiningLoops ) {
          var newFace = new TESSface();  
  
          /* We split one loop into two -- the new loop is eDst->Lface.
          * Make sure the old face points to a valid half-edge.
          */
          this.makeFace_( newFace, eDst, eOrg.Lface );
          eOrg.Lface.anEdge = eOrg;
        }
      },
  
      /* tessMeshDelete( eDel ) removes the edge eDel.  There are several cases:
      * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop
      * eDel->Lface is deleted.  Otherwise, we are splitting one loop into two;
      * the newly created loop will contain eDel->Dst.  If the deletion of eDel
      * would create isolated vertices, those are deleted as well.
      *
      * This function could be implemented as two calls to tessMeshSplice
      * plus a few calls to memFree, but this would allocate and delete
      * unnecessary vertices and faces.
      */
      //int tessMeshDelete( TESSmesh *mesh, TESShalfEdge *eDel )
      delete: function(eDel) {
        var eDelSym = eDel.Sym;
        var joiningLoops = false;
  
        /* First step: disconnect the origin vertex eDel->Org.  We make all
        * changes to get a consistent mesh in this "intermediate" state.
        */
        if( eDel.Lface !== eDel.Rface ) {
          /* We are joining two loops into one -- remove the left face */
          joiningLoops = true;
          this.killFace_( eDel.Lface, eDel.Rface );
        }
  
        if( eDel.Onext === eDel ) {
          this.killVertex_( eDel.Org, null );
        } else {
          /* Make sure that eDel->Org and eDel->Rface point to valid half-edges */
          eDel.Rface.anEdge = eDel.Oprev;
          eDel.Org.anEdge = eDel.Onext;
  
          this.splice_( eDel, eDel.Oprev );
          if( ! joiningLoops ) {
            var newFace = new TESSface();
  
            /* We are splitting one loop into two -- create a new loop for eDel. */
            this.makeFace_( newFace, eDel, eDel.Lface );
          }
        }
  
        /* Claim: the mesh is now in a consistent state, except that eDel->Org
        * may have been deleted.  Now we disconnect eDel->Dst.
        */
        if( eDelSym.Onext === eDelSym ) {
          this.killVertex_( eDelSym.Org, null );
          this.killFace_( eDelSym.Lface, null );
        } else {
          /* Make sure that eDel->Dst and eDel->Lface point to valid half-edges */
          eDel.Lface.anEdge = eDelSym.Oprev;
          eDelSym.Org.anEdge = eDelSym.Onext;
          this.splice_( eDelSym, eDelSym.Oprev );
        }
  
        /* Any isolated vertices or faces have already been freed. */
        this.killEdge_( eDel );
      },
  
      /******************** Other Edge Operations **********************/
  
      /* All these routines can be implemented with the basic edge
      * operations above.  They are provided for convenience and efficiency.
      */
  
  
      /* tessMeshAddEdgeVertex( eOrg ) creates a new edge eNew such that
      * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex.
      * eOrg and eNew will have the same left face.
      */
      // TESShalfEdge *tessMeshAddEdgeVertex( TESSmesh *mesh, TESShalfEdge *eOrg );
      addEdgeVertex: function(eOrg) {
        var eNew = this.makeEdge_( eOrg );
        var eNewSym = eNew.Sym;
  
        /* Connect the new edge appropriately */
        this.splice_( eNew, eOrg.Lnext );
  
        /* Set the vertex and face information */
        eNew.Org = eOrg.Dst;
  
        var newVertex = new TESSvertex();
        this.makeVertex_( newVertex, eNewSym, eNew.Org );
  
        eNew.Lface = eNewSym.Lface = eOrg.Lface;
  
        return eNew;
      },
  
  
      /* tessMeshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew,
      * such that eNew == eOrg->Lnext.  The new vertex is eOrg->Dst == eNew->Org.
      * eOrg and eNew will have the same left face.
      */
      // TESShalfEdge *tessMeshSplitEdge( TESSmesh *mesh, TESShalfEdge *eOrg );
      splitEdge: function(eOrg, eDst) {
        var tempHalfEdge = this.addEdgeVertex( eOrg );
        var eNew = tempHalfEdge.Sym;
  
        /* Disconnect eOrg from eOrg->Dst and connect it to eNew->Org */
        this.splice_( eOrg.Sym, eOrg.Sym.Oprev );
        this.splice_( eOrg.Sym, eNew );
  
        /* Set the vertex and face information */
        eOrg.Dst = eNew.Org;
        eNew.Dst.anEdge = eNew.Sym;	/* may have pointed to eOrg->Sym */
        eNew.Rface = eOrg.Rface;
        eNew.winding = eOrg.winding;	/* copy old winding information */
        eNew.Sym.winding = eOrg.Sym.winding;
  
        return eNew;
      },
  
  
      /* tessMeshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst
      * to eDst->Org, and returns the corresponding half-edge eNew.
      * If eOrg->Lface == eDst->Lface, this splits one loop into two,
      * and the newly created loop is eNew->Lface.  Otherwise, two disjoint
      * loops are merged into one, and the loop eDst->Lface is destroyed.
      *
      * If (eOrg == eDst), the new face will have only two edges.
      * If (eOrg->Lnext == eDst), the old face is reduced to a single edge.
      * If (eOrg->Lnext->Lnext == eDst), the old face is reduced to two edges.
      */
  
      // TESShalfEdge *tessMeshConnect( TESSmesh *mesh, TESShalfEdge *eOrg, TESShalfEdge *eDst );
      connect: function(eOrg, eDst) {
        var joiningLoops = false;  
        var eNew = this.makeEdge_( eOrg );
        var eNewSym = eNew.Sym;
  
        if( eDst.Lface !== eOrg.Lface ) {
          /* We are connecting two disjoint loops -- destroy eDst->Lface */
          joiningLoops = true;
          this.killFace_( eDst.Lface, eOrg.Lface );
        }
  
        /* Connect the new edge appropriately */
        this.splice_( eNew, eOrg.Lnext );
        this.splice_( eNewSym, eDst );
  
        /* Set the vertex and face information */
        eNew.Org = eOrg.Dst;
        eNewSym.Org = eDst.Org;
        eNew.Lface = eNewSym.Lface = eOrg.Lface;
  
        /* Make sure the old face points to a valid half-edge */
        eOrg.Lface.anEdge = eNewSym;
  
        if( ! joiningLoops ) {
          var newFace = new TESSface();
          /* We split one loop into two -- the new loop is eNew->Lface */
          this.makeFace_( newFace, eNew, eOrg.Lface );
        }
        return eNew;
      },
  
      /* tessMeshZapFace( fZap ) destroys a face and removes it from the
      * global face list.  All edges of fZap will have a NULL pointer as their
      * left face.  Any edges which also have a NULL pointer as their right face
      * are deleted entirely (along with any isolated vertices this produces).
      * An entire mesh can be deleted by zapping its faces, one at a time,
      * in any order.  Zapped faces cannot be used in further mesh operations!
      */
      zapFace: function( fZap )
      {
        var eStart = fZap.anEdge;
        var e, eNext, eSym;
        var fPrev, fNext;
  
        /* walk around face, deleting edges whose right face is also NULL */
        eNext = eStart.Lnext;
        do {
          e = eNext;
          eNext = e.Lnext;
  
          e.Lface = null;
          if( e.Rface === null ) {
            /* delete the edge -- see TESSmeshDelete above */
  
            if( e.Onext === e ) {
              this.killVertex_( e.Org, null );
            } else {
              /* Make sure that e->Org points to a valid half-edge */
              e.Org.anEdge = e.Onext;
              this.splice_( e, e.Oprev );
            }
            eSym = e.Sym;
            if( eSym.Onext === eSym ) {
              this.killVertex_( eSym.Org, null );
            } else {
              /* Make sure that eSym->Org points to a valid half-edge */
              eSym.Org.anEdge = eSym.Onext;
              this.splice_( eSym, eSym.Oprev );
            }
            this.killEdge_( e );
          }
        } while( e != eStart );
  
        /* delete from circular doubly-linked list */
        fPrev = fZap.prev;
        fNext = fZap.next;
        fNext.prev = fPrev;
        fPrev.next = fNext;
      },
  
      countFaceVerts_: function(f) {
        var eCur = f.anEdge;
        var n = 0;
        do
        {
          n++;
          eCur = eCur.Lnext;
        }
        while (eCur !== f.anEdge);
        return n;
      },
  
      //int tessMeshMergeConvexFaces( TESSmesh *mesh, int maxVertsPerFace )
      mergeConvexFaces: function(maxVertsPerFace) {
        var f;
        var eCur, eNext, eSym;
        var vStart;
        var curNv, symNv;
  
        for( f = this.fHead.next; f !== this.fHead; f = f.next )
        {
          // Skip faces which are outside the result.
          if( !f.inside )
            continue;
  
          eCur = f.anEdge;
          vStart = eCur.Org;
            
          while (true)
          {
            eNext = eCur.Lnext;
            eSym = eCur.Sym;
  
            // Try to merge if the neighbour face is valid.
            if( eSym && eSym.Lface && eSym.Lface.inside )
            {
              // Try to merge the neighbour faces if the resulting polygons
              // does not exceed maximum number of vertices.
              curNv = this.countFaceVerts_( f );
              symNv = this.countFaceVerts_( eSym.Lface );
              if( (curNv+symNv-2) <= maxVertsPerFace )
              {
                // Merge if the resulting poly is convex.
                if( Geom.vertCCW( eCur.Lprev.Org, eCur.Org, eSym.Lnext.Lnext.Org ) &&
                  Geom.vertCCW( eSym.Lprev.Org, eSym.Org, eCur.Lnext.Lnext.Org ) )
                {
                  eNext = eSym.Lnext;
                  this.delete( eSym );
                  eCur = null;
                  eSym = null;
                }
              }
            }
            
            if( eCur && eCur.Lnext.Org === vStart )
              break;
              
            // Continue to next edge.
            eCur = eNext;
          }
        }
        
        return true;
      },
  
      /* tessMeshCheckMesh( mesh ) checks a mesh for self-consistency.
      */
      check: function() {
        var fHead = this.fHead;
        var vHead = this.vHead;
        var eHead = this.eHead;
        var f, fPrev, v, vPrev, e, ePrev;
  
        fPrev = fHead;
        for( fPrev = fHead ; (f = fPrev.next) !== fHead; fPrev = f) {
          assert( f.prev === fPrev );
          e = f.anEdge;
          do {
            assert( e.Sym !== e );
            assert( e.Sym.Sym === e );
            assert( e.Lnext.Onext.Sym === e );
            assert( e.Onext.Sym.Lnext === e );
            assert( e.Lface === f );
            e = e.Lnext;
          } while( e !== f.anEdge );
        }
        assert( f.prev === fPrev && f.anEdge === null );
  
        vPrev = vHead;
        for( vPrev = vHead ; (v = vPrev.next) !== vHead; vPrev = v) {
          assert( v.prev === vPrev );
          e = v.anEdge;
          do {
            assert( e.Sym !== e );
            assert( e.Sym.Sym === e );
            assert( e.Lnext.Onext.Sym === e );
            assert( e.Onext.Sym.Lnext === e );
            assert( e.Org === v );
            e = e.Onext;
          } while( e !== v.anEdge );
        }
        assert( v.prev === vPrev && v.anEdge === null );
  
        ePrev = eHead;
        for( ePrev = eHead ; (e = ePrev.next) !== eHead; ePrev = e) {
          assert( e.Sym.next === ePrev.Sym );
          assert( e.Sym !== e );
          assert( e.Sym.Sym === e );
          assert( e.Org !== null );
          assert( e.Dst !== null );
          assert( e.Lnext.Onext.Sym === e );
          assert( e.Onext.Sym.Lnext === e );
        }
        assert( e.Sym.next === ePrev.Sym
          && e.Sym === this.eHeadSym
          && e.Sym.Sym === e
          && e.Org === null && e.Dst === null
          && e.Lface === null && e.Rface === null );
      }
  
    };
  
    var Geom = {};
  
    Geom.vertEq = function(u,v) {
      return (u.s === v.s && u.t === v.t);
    };
  
    /* Returns TRUE if u is lexicographically <= v. */
    Geom.vertLeq = function(u,v) {
      return ((u.s < v.s) || (u.s === v.s && u.t <= v.t));
    };
  
    /* Versions of VertLeq, EdgeSign, EdgeEval with s and t transposed. */
    Geom.transLeq = function(u,v) {
      return ((u.t < v.t) || (u.t === v.t && u.s <= v.s));
    };
  
    Geom.edgeGoesLeft = function(e) {
      return Geom.vertLeq( e.Dst, e.Org );
    };
  
    Geom.edgeGoesRight = function(e) {
      return Geom.vertLeq( e.Org, e.Dst );
    };
  
    Geom.vertL1dist = function(u,v) {
      return (Math.abs(u.s - v.s) + Math.abs(u.t - v.t));
    };
  
    //TESSreal tesedgeEval( TESSvertex *u, TESSvertex *v, TESSvertex *w )
    Geom.edgeEval = function( u, v, w ) {
      /* Given three vertices u,v,w such that VertLeq(u,v) && VertLeq(v,w),
      * evaluates the t-coord of the edge uw at the s-coord of the vertex v.
      * Returns v->t - (uw)(v->s), ie. the signed distance from uw to v.
      * If uw is vertical (and thus passes thru v), the result is zero.
      *
      * The calculation is extremely accurate and stable, even when v
      * is very close to u or w.  In particular if we set v->t = 0 and
      * let r be the negated result (this evaluates (uw)(v->s)), then
      * r is guaranteed to satisfy MIN(u->t,w->t) <= r <= MAX(u->t,w->t).
      */
      assert( Geom.vertLeq( u, v ) && Geom.vertLeq( v, w ));
  
      var gapL = v.s - u.s;
      var gapR = w.s - v.s;
  
      if( gapL + gapR > 0.0 ) {
        if( gapL < gapR ) {
          return (v.t - u.t) + (u.t - w.t) * (gapL / (gapL + gapR));
        } else {
          return (v.t - w.t) + (w.t - u.t) * (gapR / (gapL + gapR));
        }
      }
      /* vertical line */
      return 0.0;
    };
  
    //TESSreal tesedgeSign( TESSvertex *u, TESSvertex *v, TESSvertex *w )
    Geom.edgeSign = function( u, v, w ) {
      /* Returns a number whose sign matches EdgeEval(u,v,w) but which
      * is cheaper to evaluate.  Returns > 0, == 0 , or < 0
      * as v is above, on, or below the edge uw.
      */
      assert( Geom.vertLeq( u, v ) && Geom.vertLeq( v, w ));
  
      var gapL = v.s - u.s;
      var gapR = w.s - v.s;
  
      if( gapL + gapR > 0.0 ) {
        return (v.t - w.t) * gapL + (v.t - u.t) * gapR;
      }
      /* vertical line */
      return 0.0;
    };
  
  
    /***********************************************************************
    * Define versions of EdgeSign, EdgeEval with s and t transposed.
    */
  
    //TESSreal testransEval( TESSvertex *u, TESSvertex *v, TESSvertex *w )
    Geom.transEval = function( u, v, w ) {
      /* Given three vertices u,v,w such that TransLeq(u,v) && TransLeq(v,w),
      * evaluates the t-coord of the edge uw at the s-coord of the vertex v.
      * Returns v->s - (uw)(v->t), ie. the signed distance from uw to v.
      * If uw is vertical (and thus passes thru v), the result is zero.
      *
      * The calculation is extremely accurate and stable, even when v
      * is very close to u or w.  In particular if we set v->s = 0 and
      * let r be the negated result (this evaluates (uw)(v->t)), then
      * r is guaranteed to satisfy MIN(u->s,w->s) <= r <= MAX(u->s,w->s).
      */
      assert( Geom.transLeq( u, v ) && Geom.transLeq( v, w ));
  
      var gapL = v.t - u.t;
      var gapR = w.t - v.t;
  
      if( gapL + gapR > 0.0 ) {
        if( gapL < gapR ) {
          return (v.s - u.s) + (u.s - w.s) * (gapL / (gapL + gapR));
        } else {
          return (v.s - w.s) + (w.s - u.s) * (gapR / (gapL + gapR));
        }
      }
      /* vertical line */
      return 0.0;
    };
  
    //TESSreal testransSign( TESSvertex *u, TESSvertex *v, TESSvertex *w )
    Geom.transSign = function( u, v, w ) {
      /* Returns a number whose sign matches TransEval(u,v,w) but which
      * is cheaper to evaluate.  Returns > 0, == 0 , or < 0
      * as v is above, on, or below the edge uw.
      */
      assert( Geom.transLeq( u, v ) && Geom.transLeq( v, w ));
  
      var gapL = v.t - u.t;
      var gapR = w.t - v.t;
  
      if( gapL + gapR > 0.0 ) {
        return (v.s - w.s) * gapL + (v.s - u.s) * gapR;
      }
      /* vertical line */
      return 0.0;
    };
  
  
    //int tesvertCCW( TESSvertex *u, TESSvertex *v, TESSvertex *w )
    Geom.vertCCW = function( u, v, w ) {
      /* For almost-degenerate situations, the results are not reliable.
      * Unless the floating-point arithmetic can be performed without
      * rounding errors, *any* implementation will give incorrect results
      * on some degenerate inputs, so the client must have some way to
      * handle this situation.
      */
      return (u.s*(v.t - w.t) + v.s*(w.t - u.t) + w.s*(u.t - v.t)) >= 0.0;
    };
  
    /* Given parameters a,x,b,y returns the value (b*x+a*y)/(a+b),
    * or (x+y)/2 if a==b==0.  It requires that a,b >= 0, and enforces
    * this in the rare case that one argument is slightly negative.
    * The implementation is extremely stable numerically.
    * In particular it guarantees that the result r satisfies
    * MIN(x,y) <= r <= MAX(x,y), and the results are very accurate
    * even when a and b differ greatly in magnitude.
    */
    Geom.interpolate = function(a,x,b,y) {
      return (a = (a < 0) ? 0 : a, b = (b < 0) ? 0 : b, ((a <= b) ? ((b == 0) ? ((x+y) / 2) : (x + (y-x) * (a/(a+b)))) : (y + (x-y) * (b/(a+b)))));
    };
  
    /*
    #ifndef FOR_TRITE_TEST_PROGRAM
    #define Interpolate(a,x,b,y)	RealInterpolate(a,x,b,y)
    #else
  
    // Claim: the ONLY property the sweep algorithm relies on is that
    // MIN(x,y) <= r <= MAX(x,y).  This is a nasty way to test that.
    #include <stdlib.h>
    extern int RandomInterpolate;
  
    double Interpolate( double a, double x, double b, double y)
    {
      printf("*********************%d\n",RandomInterpolate);
      if( RandomInterpolate ) {
        a = 1.2 * drand48() - 0.1;
        a = (a < 0) ? 0 : ((a > 1) ? 1 : a);
        b = 1.0 - a;
      }
      return RealInterpolate(a,x,b,y);
    }
    #endif*/
  
    Geom.intersect = function( o1, d1, o2, d2, v ) {
      /* Given edges (o1,d1) and (o2,d2), compute their point of intersection.
      * The computed point is guaranteed to lie in the intersection of the
      * bounding rectangles defined by each edge.
      */
      var z1, z2;
      var t;
  
      /* This is certainly not the most efficient way to find the intersection
      * of two line segments, but it is very numerically stable.
      *
      * Strategy: find the two middle vertices in the VertLeq ordering,
      * and interpolate the intersection s-value from these.  Then repeat
      * using the TransLeq ordering to find the intersection t-value.
      */
  
      if( ! Geom.vertLeq( o1, d1 )) { t = o1; o1 = d1; d1 = t; } //swap( o1, d1 ); }
      if( ! Geom.vertLeq( o2, d2 )) { t = o2; o2 = d2; d2 = t; } //swap( o2, d2 ); }
      if( ! Geom.vertLeq( o1, o2 )) { t = o1; o1 = o2; o2 = t; t = d1; d1 = d2; d2 = t; }//swap( o1, o2 ); swap( d1, d2 ); }
  
      if( ! Geom.vertLeq( o2, d1 )) {
        /* Technically, no intersection -- do our best */
        v.s = (o2.s + d1.s) / 2;
      } else if( Geom.vertLeq( d1, d2 )) {
        /* Interpolate between o2 and d1 */
        z1 = Geom.edgeEval( o1, o2, d1 );
        z2 = Geom.edgeEval( o2, d1, d2 );
        if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; }
        v.s = Geom.interpolate( z1, o2.s, z2, d1.s );
      } else {
        /* Interpolate between o2 and d2 */
        z1 = Geom.edgeSign( o1, o2, d1 );
        z2 = -Geom.edgeSign( o1, d2, d1 );
        if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; }
        v.s = Geom.interpolate( z1, o2.s, z2, d2.s );
      }
  
      /* Now repeat the process for t */
  
      if( ! Geom.transLeq( o1, d1 )) { t = o1; o1 = d1; d1 = t; } //swap( o1, d1 ); }
      if( ! Geom.transLeq( o2, d2 )) { t = o2; o2 = d2; d2 = t; } //swap( o2, d2 ); }
      if( ! Geom.transLeq( o1, o2 )) { t = o1; o1 = o2; o2 = t; t = d1; d1 = d2; d2 = t; } //swap( o1, o2 ); swap( d1, d2 ); }
  
      if( ! Geom.transLeq( o2, d1 )) {
        /* Technically, no intersection -- do our best */
        v.t = (o2.t + d1.t) / 2;
      } else if( Geom.transLeq( d1, d2 )) {
        /* Interpolate between o2 and d1 */
        z1 = Geom.transEval( o1, o2, d1 );
        z2 = Geom.transEval( o2, d1, d2 );
        if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; }
        v.t = Geom.interpolate( z1, o2.t, z2, d1.t );
      } else {
        /* Interpolate between o2 and d2 */
        z1 = Geom.transSign( o1, o2, d1 );
        z2 = -Geom.transSign( o1, d2, d1 );
        if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; }
        v.t = Geom.interpolate( z1, o2.t, z2, d2.t );
      }
    };
  
  
  
    function DictNode() {
      this.key = null;
      this.next = null;
      this.prev = null;
    };
  
    function Dict(frame, leq) {
      this.head = new DictNode();
      this.head.next = this.head;
      this.head.prev = this.head;
      this.frame = frame;
      this.leq = leq;
    };
  
    Dict.prototype = {
      min: function() {
        return this.head.next;
      },
  
      max: function() {
        return this.head.prev;
      },
  
      insert: function(k) {
        return this.insertBefore(this.head, k);
      },
  
      search: function(key) {
        /* Search returns the node with the smallest key greater than or equal
        * to the given key.  If there is no such key, returns a node whose
        * key is NULL.  Similarly, Succ(Max(d)) has a NULL key, etc.
        */
        var node = this.head;
        do {
          node = node.next;
        } while( node.key !== null && ! this.leq(this.frame, key, node.key));
  
        return node;
      },
  
      insertBefore: function(node, key) {
        do {
          node = node.prev;
        } while( node.key !== null && ! this.leq(this.frame, node.key, key));
  
        var newNode = new DictNode();
        newNode.key = key;
        newNode.next = node.next;
        node.next.prev = newNode;
        newNode.prev = node;
        node.next = newNode;
  
        return newNode;
      },
  
      delete: function(node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
      }
    };
  
  
    function PQnode() {
      this.handle = null;
    }
  
    function PQhandleElem() {
      this.key = null;
      this.node = null;
    }
  
    function PriorityQ(size, leq) {
      this.size = 0;
      this.max = size;
  
      this.nodes = [];
      this.nodes.length = size+1;
      for (var i = 0; i < this.nodes.length; i++)
        this.nodes[i] = new PQnode();
  
      this.handles = [];
      this.handles.length = size+1;
      for (var i = 0; i < this.handles.length; i++)
        this.handles[i] = new PQhandleElem();
  
      this.initialized = false;
      this.freeList = 0;
      this.leq = leq;
  
      this.nodes[1].handle = 1;	/* so that Minimum() returns NULL */
      this.handles[1].key = null;
    };
  
    PriorityQ.prototype = {
  
      floatDown_: function( curr )
      {
        var n = this.nodes;
        var h = this.handles;
        var hCurr, hChild;
        var child;
  
        hCurr = n[curr].handle;
        for( ;; ) {
          child = curr << 1;
          if( child < this.size && this.leq( h[n[child+1].handle].key, h[n[child].handle].key )) {
            ++child;
          }
  
          assert(child <= this.max);
  
          hChild = n[child].handle;
          if( child > this.size || this.leq( h[hCurr].key, h[hChild].key )) {
            n[curr].handle = hCurr;
            h[hCurr].node = curr;
            break;
          }
          n[curr].handle = hChild;
          h[hChild].node = curr;
          curr = child;
        }
      },
  
      floatUp_: function( curr )
      {
        var n = this.nodes;
        var h = this.handles;
        var hCurr, hParent;
        var parent;
  
        hCurr = n[curr].handle;
        for( ;; ) {
          parent = curr >> 1;
          hParent = n[parent].handle;
          if( parent == 0 || this.leq( h[hParent].key, h[hCurr].key )) {
            n[curr].handle = hCurr;
            h[hCurr].node = curr;
            break;
          }
          n[curr].handle = hParent;
          h[hParent].node = curr;
          curr = parent;
        }
      },
  
      init: function() {
        /* This method of building a heap is O(n), rather than O(n lg n). */
        for( var i = this.size; i >= 1; --i ) {
          this.floatDown_( i );
        }
        this.initialized = true;
      },
  
      min: function() {
        return this.handles[this.nodes[1].handle].key;
      },
  
      isEmpty: function() {
        this.size === 0;
      },
  
      /* really pqHeapInsert */
      /* returns INV_HANDLE iff out of memory */
      //PQhandle pqHeapInsert( TESSalloc* alloc, PriorityQHeap *pq, PQkey keyNew )
      insert: function(keyNew)
      {
        var curr;
        var free;
  
        curr = ++this.size;
        if( (curr*2) > this.max ) {
          this.max *= 2;
          var s;
          s = this.nodes.length;
          this.nodes.length = this.max+1;
          for (var i = s; i < this.nodes.length; i++)
            this.nodes[i] = new PQnode();
  
          s = this.handles.length;
          this.handles.length = this.max+1;
          for (var i = s; i < this.handles.length; i++)
            this.handles[i] = new PQhandleElem();
        }
  
        if( this.freeList === 0 ) {
          free = curr;
        } else {
          free = this.freeList;
          this.freeList = this.handles[free].node;
        }
  
        this.nodes[curr].handle = free;
        this.handles[free].node = curr;
        this.handles[free].key = keyNew;
  
        if( this.initialized ) {
          this.floatUp_( curr );
        }
        return free;
      },
  
      //PQkey pqHeapExtractMin( PriorityQHeap *pq )
      extractMin: function() {
        var n = this.nodes;
        var h = this.handles;
        var hMin = n[1].handle;
        var min = h[hMin].key;
  
        if( this.size > 0 ) {
          n[1].handle = n[this.size].handle;
          h[n[1].handle].node = 1;
  
          h[hMin].key = null;
          h[hMin].node = this.freeList;
          this.freeList = hMin;
  
          --this.size;
          if( this.size > 0 ) {
            this.floatDown_( 1 );
          }
        }
        return min;
      },
  
      delete: function( hCurr ) {
        var n = this.nodes;
        var h = this.handles;
        var curr;
  
        assert( hCurr >= 1 && hCurr <= this.max && h[hCurr].key !== null );
  
        curr = h[hCurr].node;
        n[curr].handle = n[this.size].handle;
        h[n[curr].handle].node = curr;
  
        --this.size;
        if( curr <= this.size ) {
          if( curr <= 1 || this.leq( h[n[curr>>1].handle].key, h[n[curr].handle].key )) {
            this.floatDown_( curr );
          } else {
            this.floatUp_( curr );
          }
        }
        h[hCurr].key = null;
        h[hCurr].node = this.freeList;
        this.freeList = hCurr;
      }
    };
  
  
    /* For each pair of adjacent edges crossing the sweep line, there is
    * an ActiveRegion to represent the region between them.  The active
    * regions are kept in sorted order in a dynamic dictionary.  As the
    * sweep line crosses each vertex, we update the affected regions.
    */
  
    function ActiveRegion() {
      this.eUp = null;		/* upper edge, directed right to left */
      this.nodeUp = null;	/* dictionary node corresponding to eUp */
      this.windingNumber = 0;	/* used to determine which regions are
                  * inside the polygon */
      this.inside = false;		/* is this region inside the polygon? */
      this.sentinel = false;	/* marks fake edges at t = +/-infinity */
      this.dirty = false;		/* marks regions where the upper or lower
              * edge has changed, but we haven't checked
              * whether they intersect yet */
      this.fixUpperEdge = false;	/* marks temporary edges introduced when
                * we process a "right vertex" (one without
                * any edges leaving to the right) */
    };
  
    var Sweep = {};
  
    Sweep.regionBelow = function(r) {
      return r.nodeUp.prev.key;
    }
  
    Sweep.regionAbove = function(r) {
      return r.nodeUp.next.key;
    }
  
    Sweep.debugEvent = function( tess ) {
      // empty
    }
  
  
    /*
    * Invariants for the Edge Dictionary.
    * - each pair of adjacent edges e2=Succ(e1) satisfies EdgeLeq(e1,e2)
    *   at any valid location of the sweep event
    * - if EdgeLeq(e2,e1) as well (at any valid sweep event), then e1 and e2
    *   share a common endpoint
    * - for each e, e->Dst has been processed, but not e->Org
    * - each edge e satisfies VertLeq(e->Dst,event) && VertLeq(event,e->Org)
    *   where "event" is the current sweep line event.
    * - no edge e has zero length
    *
    * Invariants for the Mesh (the processed portion).
    * - the portion of the mesh left of the sweep line is a planar graph,
    *   ie. there is *some* way to embed it in the plane
    * - no processed edge has zero length
    * - no two processed vertices have identical coordinates
    * - each "inside" region is monotone, ie. can be broken into two chains
    *   of monotonically increasing vertices according to VertLeq(v1,v2)
    *   - a non-invariant: these chains may intersect (very slightly)
    *
    * Invariants for the Sweep.
    * - if none of the edges incident to the event vertex have an activeRegion
    *   (ie. none of these edges are in the edge dictionary), then the vertex
    *   has only right-going edges.
    * - if an edge is marked "fixUpperEdge" (it is a temporary edge introduced
    *   by ConnectRightVertex), then it is the only right-going edge from
    *   its associated vertex.  (This says that these edges exist only
    *   when it is necessary.)
    */
  
    /* When we merge two edges into one, we need to compute the combined
    * winding of the new edge.
    */
    Sweep.addWinding = function(eDst,eSrc) {
      eDst.winding += eSrc.winding;
      eDst.Sym.winding += eSrc.Sym.winding;
    }
  
  
    //static int EdgeLeq( TESStesselator *tess, ActiveRegion *reg1, ActiveRegion *reg2 )
    Sweep.edgeLeq = function( tess, reg1, reg2 ) {
      /*
      * Both edges must be directed from right to left (this is the canonical
      * direction for the upper edge of each region).
      *
      * The strategy is to evaluate a "t" value for each edge at the
      * current sweep line position, given by tess->event.  The calculations
      * are designed to be very stable, but of course they are not perfect.
      *
      * Special case: if both edge destinations are at the sweep event,
      * we sort the edges by slope (they would otherwise compare equally).
      */
      var ev = tess.event;
      var t1, t2;
  
      var e1 = reg1.eUp;
      var e2 = reg2.eUp;
  
      if( e1.Dst === ev ) {
        if( e2.Dst === ev ) {
          /* Two edges right of the sweep line which meet at the sweep event.
          * Sort them by slope.
          */
          if( Geom.vertLeq( e1.Org, e2.Org )) {
            return Geom.edgeSign( e2.Dst, e1.Org, e2.Org ) <= 0;
          }
          return Geom.edgeSign( e1.Dst, e2.Org, e1.Org ) >= 0;
        }
        return Geom.edgeSign( e2.Dst, ev, e2.Org ) <= 0;
      }
      if( e2.Dst === ev ) {
        return Geom.edgeSign( e1.Dst, ev, e1.Org ) >= 0;
      }
  
      /* General case - compute signed distance *from* e1, e2 to event */
      var t1 = Geom.edgeEval( e1.Dst, ev, e1.Org );
      var t2 = Geom.edgeEval( e2.Dst, ev, e2.Org );
      return (t1 >= t2);
    }
  
  
    //static void DeleteRegion( TESStesselator *tess, ActiveRegion *reg )
    Sweep.deleteRegion = function( tess, reg ) {
      if( reg.fixUpperEdge ) {
        /* It was created with zero winding number, so it better be
        * deleted with zero winding number (ie. it better not get merged
        * with a real edge).
        */
        assert( reg.eUp.winding === 0 );
      }
      reg.eUp.activeRegion = null;
      tess.dict.delete( reg.nodeUp );
    }
  
    //static int FixUpperEdge( TESStesselator *tess, ActiveRegion *reg, TESShalfEdge *newEdge )
    Sweep.fixUpperEdge = function( tess, reg, newEdge ) {
      /*
      * Replace an upper edge which needs fixing (see ConnectRightVertex).
      */
      assert( reg.fixUpperEdge );
      tess.mesh.delete( reg.eUp );
      reg.fixUpperEdge = false;
      reg.eUp = newEdge;
      newEdge.activeRegion = reg;
    }
  
    //static ActiveRegion *TopLeftRegion( TESStesselator *tess, ActiveRegion *reg )
    Sweep.topLeftRegion = function( tess, reg ) {
      var org = reg.eUp.Org;
      var e;
  
      /* Find the region above the uppermost edge with the same origin */
      do {
        reg = Sweep.regionAbove( reg );
      } while( reg.eUp.Org === org );
  
      /* If the edge above was a temporary edge introduced by ConnectRightVertex,
      * now is the time to fix it.
      */
      if( reg.fixUpperEdge ) {
        e = tess.mesh.connect( Sweep.regionBelow(reg).eUp.Sym, reg.eUp.Lnext );
        if (e === null) return null;
        Sweep.fixUpperEdge( tess, reg, e );
        reg = Sweep.regionAbove( reg );
      }
      return reg;
    }
  
    //static ActiveRegion *TopRightRegion( ActiveRegion *reg )
    Sweep.topRightRegion = function( reg )
    {
      var dst = reg.eUp.Dst;
      var reg = null;
      /* Find the region above the uppermost edge with the same destination */
      do {
        reg = Sweep.regionAbove( reg );
      } while( reg.eUp.Dst === dst );
      return reg;
    }
  
    //static ActiveRegion *AddRegionBelow( TESStesselator *tess, ActiveRegion *regAbove, TESShalfEdge *eNewUp )
    Sweep.addRegionBelow = function( tess, regAbove, eNewUp ) {
      /*
      * Add a new active region to the sweep line, *somewhere* below "regAbove"
      * (according to where the new edge belongs in the sweep-line dictionary).
      * The upper edge of the new region will be "eNewUp".
      * Winding number and "inside" flag are not updated.
      */
      var regNew = new ActiveRegion();
      regNew.eUp = eNewUp;
      regNew.nodeUp = tess.dict.insertBefore( regAbove.nodeUp, regNew );
    //	if (regNew->nodeUp == NULL) longjmp(tess->env,1);
      regNew.fixUpperEdge = false;
      regNew.sentinel = false;
      regNew.dirty = false;
  
      eNewUp.activeRegion = regNew;
      return regNew;
    }
  
    //static int IsWindingInside( TESStesselator *tess, int n )
    Sweep.isWindingInside = function( tess, n ) {
      switch( tess.windingRule ) {
        case Tess2.WINDING_ODD:
          return (n & 1) != 0;
        case Tess2.WINDING_NONZERO:
          return (n != 0);
        case Tess2.WINDING_POSITIVE:
          return (n > 0);
        case Tess2.WINDING_NEGATIVE:
          return (n < 0);
        case Tess2.WINDING_ABS_GEQ_TWO:
          return (n >= 2) || (n <= -2);
      }
      assert( false );
      return false;
    }
  
    //static void ComputeWinding( TESStesselator *tess, ActiveRegion *reg )
    Sweep.computeWinding = function( tess, reg ) {
      reg.windingNumber = Sweep.regionAbove(reg).windingNumber + reg.eUp.winding;
      reg.inside = Sweep.isWindingInside( tess, reg.windingNumber );
    }
  
  
    //static void FinishRegion( TESStesselator *tess, ActiveRegion *reg )
    Sweep.finishRegion = function( tess, reg ) {
      /*
      * Delete a region from the sweep line.  This happens when the upper
      * and lower chains of a region meet (at a vertex on the sweep line).
      * The "inside" flag is copied to the appropriate mesh face (we could
      * not do this before -- since the structure of the mesh is always
      * changing, this face may not have even existed until now).
      */
      var e = reg.eUp;
      var f = e.Lface;
  
      f.inside = reg.inside;
      f.anEdge = e;   /* optimization for tessMeshTessellateMonoRegion() */
      Sweep.deleteRegion( tess, reg );
    }
  
  
    //static TESShalfEdge *FinishLeftRegions( TESStesselator *tess, ActiveRegion *regFirst, ActiveRegion *regLast )
    Sweep.finishLeftRegions = function( tess, regFirst, regLast ) {
      /*
      * We are given a vertex with one or more left-going edges.  All affected
      * edges should be in the edge dictionary.  Starting at regFirst->eUp,
      * we walk down deleting all regions where both edges have the same
      * origin vOrg.  At the same time we copy the "inside" flag from the
      * active region to the face, since at this point each face will belong
      * to at most one region (this was not necessarily true until this point
      * in the sweep).  The walk stops at the region above regLast; if regLast
      * is NULL we walk as far as possible.  At the same time we relink the
      * mesh if necessary, so that the ordering of edges around vOrg is the
      * same as in the dictionary.
      */
      var e, ePrev;
      var reg = null;
      var regPrev = regFirst;
      var ePrev = regFirst.eUp;
      while( regPrev !== regLast ) {
        regPrev.fixUpperEdge = false;	/* placement was OK */
        reg = Sweep.regionBelow( regPrev );
        e = reg.eUp;
        if( e.Org != ePrev.Org ) {
          if( ! reg.fixUpperEdge ) {
            /* Remove the last left-going edge.  Even though there are no further
            * edges in the dictionary with this origin, there may be further
            * such edges in the mesh (if we are adding left edges to a vertex
            * that has already been processed).  Thus it is important to call
            * FinishRegion rather than just DeleteRegion.
            */
            Sweep.finishRegion( tess, regPrev );
            break;
          }
          /* If the edge below was a temporary edge introduced by
          * ConnectRightVertex, now is the time to fix it.
          */
          e = tess.mesh.connect( ePrev.Lprev, e.Sym );
    //			if (e == NULL) longjmp(tess->env,1);
          Sweep.fixUpperEdge( tess, reg, e );
        }
  
        /* Relink edges so that ePrev->Onext == e */
        if( ePrev.Onext !== e ) {
          tess.mesh.splice( e.Oprev, e );
          tess.mesh.splice( ePrev, e );
        }
        Sweep.finishRegion( tess, regPrev );	/* may change reg->eUp */
        ePrev = reg.eUp;
        regPrev = reg;
      }
      return ePrev;
    }
  
  
    //static void AddRightEdges( TESStesselator *tess, ActiveRegion *regUp, TESShalfEdge *eFirst, TESShalfEdge *eLast, TESShalfEdge *eTopLeft, int cleanUp )
    Sweep.addRightEdges = function( tess, regUp, eFirst, eLast, eTopLeft, cleanUp ) {
      /*
      * Purpose: insert right-going edges into the edge dictionary, and update
      * winding numbers and mesh connectivity appropriately.  All right-going
      * edges share a common origin vOrg.  Edges are inserted CCW starting at
      * eFirst; the last edge inserted is eLast->Oprev.  If vOrg has any
      * left-going edges already processed, then eTopLeft must be the edge
      * such that an imaginary upward vertical segment from vOrg would be
      * contained between eTopLeft->Oprev and eTopLeft; otherwise eTopLeft
      * should be NULL.
      */
      var reg, regPrev;
      var e, ePrev;
      var firstTime = true;
  
      /* Insert the new right-going edges in the dictionary */
      e = eFirst;
      do {
        assert( Geom.vertLeq( e.Org, e.Dst ));
        Sweep.addRegionBelow( tess, regUp, e.Sym );
        e = e.Onext;
      } while ( e !== eLast );
  
      /* Walk *all* right-going edges from e->Org, in the dictionary order,
      * updating the winding numbers of each region, and re-linking the mesh
      * edges to match the dictionary ordering (if necessary).
      */
      if( eTopLeft === null ) {
        eTopLeft = Sweep.regionBelow( regUp ).eUp.Rprev;
      }
      regPrev = regUp;
      ePrev = eTopLeft;
      for( ;; ) {
        reg = Sweep.regionBelow( regPrev );
        e = reg.eUp.Sym;
        if( e.Org !== ePrev.Org ) break;
  
        if( e.Onext !== ePrev ) {
          /* Unlink e from its current position, and relink below ePrev */
          tess.mesh.splice( e.Oprev, e );
          tess.mesh.splice( ePrev.Oprev, e );
        }
        /* Compute the winding number and "inside" flag for the new regions */
        reg.windingNumber = regPrev.windingNumber - e.winding;
        reg.inside = Sweep.isWindingInside( tess, reg.windingNumber );
  
        /* Check for two outgoing edges with same slope -- process these
        * before any intersection tests (see example in tessComputeInterior).
        */
        regPrev.dirty = true;
        if( ! firstTime && Sweep.checkForRightSplice( tess, regPrev )) {
          Sweep.addWinding( e, ePrev );
          Sweep.deleteRegion( tess, regPrev );
          tess.mesh.delete( ePrev );
        }
        firstTime = false;
        regPrev = reg;
        ePrev = e;
      }
      regPrev.dirty = true;
      assert( regPrev.windingNumber - e.winding === reg.windingNumber );
  
      if( cleanUp ) {
        /* Check for intersections between newly adjacent edges. */
        Sweep.walkDirtyRegions( tess, regPrev );
      }
    }
  
  
    //static void SpliceMergeVertices( TESStesselator *tess, TESShalfEdge *e1, TESShalfEdge *e2 )
    Sweep.spliceMergeVertices = function( tess, e1, e2 ) {
      /*
      * Two vertices with idential coordinates are combined into one.
      * e1->Org is kept, while e2->Org is discarded.
      */
      tess.mesh.splice( e1, e2 ); 
    }
  
    //static void VertexWeights( TESSvertex *isect, TESSvertex *org, TESSvertex *dst, TESSreal *weights )
    Sweep.vertexWeights = function( isect, org, dst ) {
      /*
      * Find some weights which describe how the intersection vertex is
      * a linear combination of "org" and "dest".  Each of the two edges
      * which generated "isect" is allocated 50% of the weight; each edge
      * splits the weight between its org and dst according to the
      * relative distance to "isect".
      */
      var t1 = Geom.vertL1dist( org, isect );
      var t2 = Geom.vertL1dist( dst, isect );
      var w0 = 0.5 * t2 / (t1 + t2);
      var w1 = 0.5 * t1 / (t1 + t2);
      isect.coords[0] += w0*org.coords[0] + w1*dst.coords[0];
      isect.coords[1] += w0*org.coords[1] + w1*dst.coords[1];
      isect.coords[2] += w0*org.coords[2] + w1*dst.coords[2];
    }
  
  
    //static void GetIntersectData( TESStesselator *tess, TESSvertex *isect, TESSvertex *orgUp, TESSvertex *dstUp, TESSvertex *orgLo, TESSvertex *dstLo )
    Sweep.getIntersectData = function( tess, isect, orgUp, dstUp, orgLo, dstLo ) {
       /*
       * We've computed a new intersection point, now we need a "data" pointer
       * from the user so that we can refer to this new vertex in the
       * rendering callbacks.
       */
      isect.coords[0] = isect.coords[1] = isect.coords[2] = 0;
      isect.idx = -1;
      Sweep.vertexWeights( isect, orgUp, dstUp );
      Sweep.vertexWeights( isect, orgLo, dstLo );
    }
  
    //static int CheckForRightSplice( TESStesselator *tess, ActiveRegion *regUp )
    Sweep.checkForRightSplice = function( tess, regUp ) {
      /*
      * Check the upper and lower edge of "regUp", to make sure that the
      * eUp->Org is above eLo, or eLo->Org is below eUp (depending on which
      * origin is leftmost).
      *
      * The main purpose is to splice right-going edges with the same
      * dest vertex and nearly identical slopes (ie. we can't distinguish
      * the slopes numerically).  However the splicing can also help us
      * to recover from numerical errors.  For example, suppose at one
      * point we checked eUp and eLo, and decided that eUp->Org is barely
      * above eLo.  Then later, we split eLo into two edges (eg. from
      * a splice operation like this one).  This can change the result of
      * our test so that now eUp->Org is incident to eLo, or barely below it.
      * We must correct this condition to maintain the dictionary invariants.
      *
      * One possibility is to check these edges for intersection again
      * (ie. CheckForIntersect).  This is what we do if possible.  However
      * CheckForIntersect requires that tess->event lies between eUp and eLo,
      * so that it has something to fall back on when the intersection
      * calculation gives us an unusable answer.  So, for those cases where
      * we can't check for intersection, this routine fixes the problem
      * by just splicing the offending vertex into the other edge.
      * This is a guaranteed solution, no matter how degenerate things get.
      * Basically this is a combinatorial solution to a numerical problem.
      */
      var regLo = Sweep.regionBelow(regUp);
      var eUp = regUp.eUp;
      var eLo = regLo.eUp;
  
      if( Geom.vertLeq( eUp.Org, eLo.Org )) {
        if( Geom.edgeSign( eLo.Dst, eUp.Org, eLo.Org ) > 0 ) return false;
  
        /* eUp->Org appears to be below eLo */
        if( ! Geom.vertEq( eUp.Org, eLo.Org )) {
          /* Splice eUp->Org into eLo */
          tess.mesh.splitEdge( eLo.Sym );
          tess.mesh.splice( eUp, eLo.Oprev );
          regUp.dirty = regLo.dirty = true;
  
        } else if( eUp.Org !== eLo.Org ) {
          /* merge the two vertices, discarding eUp->Org */
          tess.pq.delete( eUp.Org.pqHandle );
          Sweep.spliceMergeVertices( tess, eLo.Oprev, eUp );
        }
      } else {
        if( Geom.edgeSign( eUp.Dst, eLo.Org, eUp.Org ) < 0 ) return false;
  
        /* eLo->Org appears to be above eUp, so splice eLo->Org into eUp */
        Sweep.regionAbove(regUp).dirty = regUp.dirty = true;
        tess.mesh.splitEdge( eUp.Sym );
        tess.mesh.splice( eLo.Oprev, eUp );
      }
      return true;
    }
  
    //static int CheckForLeftSplice( TESStesselator *tess, ActiveRegion *regUp )
    Sweep.checkForLeftSplice = function( tess, regUp ) {
      /*
      * Check the upper and lower edge of "regUp", to make sure that the
      * eUp->Dst is above eLo, or eLo->Dst is below eUp (depending on which
      * destination is rightmost).
      *
      * Theoretically, this should always be true.  However, splitting an edge
      * into two pieces can change the results of previous tests.  For example,
      * suppose at one point we checked eUp and eLo, and decided that eUp->Dst
      * is barely above eLo.  Then later, we split eLo into two edges (eg. from
      * a splice operation like this one).  This can change the result of
      * the test so that now eUp->Dst is incident to eLo, or barely below it.
      * We must correct this condition to maintain the dictionary invariants
      * (otherwise new edges might get inserted in the wrong place in the
      * dictionary, and bad stuff will happen).
      *
      * We fix the problem by just splicing the offending vertex into the
      * other edge.
      */
      var regLo = Sweep.regionBelow(regUp);
      var eUp = regUp.eUp;
      var eLo = regLo.eUp;
      var e;
  
      assert( ! Geom.vertEq( eUp.Dst, eLo.Dst ));
  
      if( Geom.vertLeq( eUp.Dst, eLo.Dst )) {
        if( Geom.edgeSign( eUp.Dst, eLo.Dst, eUp.Org ) < 0 ) return false;
  
        /* eLo->Dst is above eUp, so splice eLo->Dst into eUp */
        Sweep.regionAbove(regUp).dirty = regUp.dirty = true;
        e = tess.mesh.splitEdge( eUp );
        tess.mesh.splice( eLo.Sym, e );
        e.Lface.inside = regUp.inside;
      } else {
        if( Geom.edgeSign( eLo.Dst, eUp.Dst, eLo.Org ) > 0 ) return false;
  
        /* eUp->Dst is below eLo, so splice eUp->Dst into eLo */
        regUp.dirty = regLo.dirty = true;
        e = tess.mesh.splitEdge( eLo );
        tess.mesh.splice( eUp.Lnext, eLo.Sym );
        e.Rface.inside = regUp.inside;
      }
      return true;
    }
  
  
    //static int CheckForIntersect( TESStesselator *tess, ActiveRegion *regUp )
    Sweep.checkForIntersect = function( tess, regUp ) {
      /*
      * Check the upper and lower edges of the given region to see if
      * they intersect.  If so, create the intersection and add it
      * to the data structures.
      *
      * Returns TRUE if adding the new intersection resulted in a recursive
      * call to AddRightEdges(); in this case all "dirty" regions have been
      * checked for intersections, and possibly regUp has been deleted.
      */
      var regLo = Sweep.regionBelow(regUp);
      var eUp = regUp.eUp;
      var eLo = regLo.eUp;
      var orgUp = eUp.Org;
      var orgLo = eLo.Org;
      var dstUp = eUp.Dst;
      var dstLo = eLo.Dst;
      var tMinUp, tMaxLo;
      var isect = new TESSvertex, orgMin;
      var e;
  
      assert( ! Geom.vertEq( dstLo, dstUp ));
      assert( Geom.edgeSign( dstUp, tess.event, orgUp ) <= 0 );
      assert( Geom.edgeSign( dstLo, tess.event, orgLo ) >= 0 );
      assert( orgUp !== tess.event && orgLo !== tess.event );
      assert( ! regUp.fixUpperEdge && ! regLo.fixUpperEdge );
  
      if( orgUp === orgLo ) return false;	/* right endpoints are the same */
  
      tMinUp = Math.min( orgUp.t, dstUp.t );
      tMaxLo = Math.max( orgLo.t, dstLo.t );
      if( tMinUp > tMaxLo ) return false;	/* t ranges do not overlap */
  
      if( Geom.vertLeq( orgUp, orgLo )) {
        if( Geom.edgeSign( dstLo, orgUp, orgLo ) > 0 ) return false;
      } else {
        if( Geom.edgeSign( dstUp, orgLo, orgUp ) < 0 ) return false;
      }
  
      /* At this point the edges intersect, at least marginally */
      Sweep.debugEvent( tess );
  
      Geom.intersect( dstUp, orgUp, dstLo, orgLo, isect );
      /* The following properties are guaranteed: */
      assert( Math.min( orgUp.t, dstUp.t ) <= isect.t );
      assert( isect.t <= Math.max( orgLo.t, dstLo.t ));
      assert( Math.min( dstLo.s, dstUp.s ) <= isect.s );
      assert( isect.s <= Math.max( orgLo.s, orgUp.s ));
  
      if( Geom.vertLeq( isect, tess.event )) {
        /* The intersection point lies slightly to the left of the sweep line,
        * so move it until it''s slightly to the right of the sweep line.
        * (If we had perfect numerical precision, this would never happen
        * in the first place).  The easiest and safest thing to do is
        * replace the intersection by tess->event.
        */
        isect.s = tess.event.s;
        isect.t = tess.event.t;
      }
      /* Similarly, if the computed intersection lies to the right of the
      * rightmost origin (which should rarely happen), it can cause
      * unbelievable inefficiency on sufficiently degenerate inputs.
      * (If you have the test program, try running test54.d with the
      * "X zoom" option turned on).
      */
      orgMin = Geom.vertLeq( orgUp, orgLo ) ? orgUp : orgLo;
      if( Geom.vertLeq( orgMin, isect )) {
        isect.s = orgMin.s;
        isect.t = orgMin.t;
      }
  
      if( Geom.vertEq( isect, orgUp ) || Geom.vertEq( isect, orgLo )) {
        /* Easy case -- intersection at one of the right endpoints */
        Sweep.checkForRightSplice( tess, regUp );
        return false;
      }
  
      if(    (! Geom.vertEq( dstUp, tess.event )
        && Geom.edgeSign( dstUp, tess.event, isect ) >= 0)
        || (! Geom.vertEq( dstLo, tess.event )
        && Geom.edgeSign( dstLo, tess.event, isect ) <= 0 ))
      {
        /* Very unusual -- the new upper or lower edge would pass on the
        * wrong side of the sweep event, or through it.  This can happen
        * due to very small numerical errors in the intersection calculation.
        */
        if( dstLo === tess.event ) {
          /* Splice dstLo into eUp, and process the new region(s) */
          tess.mesh.splitEdge( eUp.Sym );
          tess.mesh.splice( eLo.Sym, eUp );
          regUp = Sweep.topLeftRegion( tess, regUp );
    //			if (regUp == NULL) longjmp(tess->env,1);
          eUp = Sweep.regionBelow(regUp).eUp;
          Sweep.finishLeftRegions( tess, Sweep.regionBelow(regUp), regLo );
          Sweep.addRightEdges( tess, regUp, eUp.Oprev, eUp, eUp, true );
          return true;
        }
        if( dstUp === tess.event ) {
          /* Splice dstUp into eLo, and process the new region(s) */
          tess.mesh.splitEdge( eLo.Sym );
          tess.mesh.splice( eUp.Lnext, eLo.Oprev ); 
          regLo = regUp;
          regUp = Sweep.topRightRegion( regUp );
          e = Sweep.regionBelow(regUp).eUp.Rprev;
          regLo.eUp = eLo.Oprev;
          eLo = Sweep.finishLeftRegions( tess, regLo, null );
          Sweep.addRightEdges( tess, regUp, eLo.Onext, eUp.Rprev, e, true );
          return true;
        }
        /* Special case: called from ConnectRightVertex.  If either
        * edge passes on the wrong side of tess->event, split it
        * (and wait for ConnectRightVertex to splice it appropriately).
        */
        if( Geom.edgeSign( dstUp, tess.event, isect ) >= 0 ) {
          Sweep.regionAbove(regUp).dirty = regUp.dirty = true;
          tess.mesh.splitEdge( eUp.Sym );
          eUp.Org.s = tess.event.s;
          eUp.Org.t = tess.event.t;
        }
        if( Geom.edgeSign( dstLo, tess.event, isect ) <= 0 ) {
          regUp.dirty = regLo.dirty = true;
          tess.mesh.splitEdge( eLo.Sym );
          eLo.Org.s = tess.event.s;
          eLo.Org.t = tess.event.t;
        }
        /* leave the rest for ConnectRightVertex */
        return false;
      }
  
      /* General case -- split both edges, splice into new vertex.
      * When we do the splice operation, the order of the arguments is
      * arbitrary as far as correctness goes.  However, when the operation
      * creates a new face, the work done is proportional to the size of
      * the new face.  We expect the faces in the processed part of
      * the mesh (ie. eUp->Lface) to be smaller than the faces in the
      * unprocessed original contours (which will be eLo->Oprev->Lface).
      */
      tess.mesh.splitEdge( eUp.Sym );
      tess.mesh.splitEdge( eLo.Sym );
      tess.mesh.splice( eLo.Oprev, eUp );
      eUp.Org.s = isect.s;
      eUp.Org.t = isect.t;
      eUp.Org.pqHandle = tess.pq.insert( eUp.Org );
      Sweep.getIntersectData( tess, eUp.Org, orgUp, dstUp, orgLo, dstLo );
      Sweep.regionAbove(regUp).dirty = regUp.dirty = regLo.dirty = true;
      return false;
    }
  
    //static void WalkDirtyRegions( TESStesselator *tess, ActiveRegion *regUp )
    Sweep.walkDirtyRegions = function( tess, regUp ) {
      /*
      * When the upper or lower edge of any region changes, the region is
      * marked "dirty".  This routine walks through all the dirty regions
      * and makes sure that the dictionary invariants are satisfied
      * (see the comments at the beginning of this file).  Of course
      * new dirty regions can be created as we make changes to restore
      * the invariants.
      */
      var regLo = Sweep.regionBelow(regUp);
      var eUp, eLo;
  
      for( ;; ) {
        /* Find the lowest dirty region (we walk from the bottom up). */
        while( regLo.dirty ) {
          regUp = regLo;
          regLo = Sweep.regionBelow(regLo);
        }
        if( ! regUp.dirty ) {
          regLo = regUp;
          regUp = Sweep.regionAbove( regUp );
          if( regUp == null || ! regUp.dirty ) {
            /* We've walked all the dirty regions */
            return;
          }
        }
        regUp.dirty = false;
        eUp = regUp.eUp;
        eLo = regLo.eUp;
  
        if( eUp.Dst !== eLo.Dst ) {
          /* Check that the edge ordering is obeyed at the Dst vertices. */
          if( Sweep.checkForLeftSplice( tess, regUp )) {
  
            /* If the upper or lower edge was marked fixUpperEdge, then
            * we no longer need it (since these edges are needed only for
            * vertices which otherwise have no right-going edges).
            */
            if( regLo.fixUpperEdge ) {
              Sweep.deleteRegion( tess, regLo );
              tess.mesh.delete( eLo );
              regLo = Sweep.regionBelow( regUp );
              eLo = regLo.eUp;
            } else if( regUp.fixUpperEdge ) {
              Sweep.deleteRegion( tess, regUp );
              tess.mesh.delete( eUp );
              regUp = Sweep.regionAbove( regLo );
              eUp = regUp.eUp;
            }
          }
        }
        if( eUp.Org !== eLo.Org ) {
          if(    eUp.Dst !== eLo.Dst
            && ! regUp.fixUpperEdge && ! regLo.fixUpperEdge
            && (eUp.Dst === tess.event || eLo.Dst === tess.event) )
          {
            /* When all else fails in CheckForIntersect(), it uses tess->event
            * as the intersection location.  To make this possible, it requires
            * that tess->event lie between the upper and lower edges, and also
            * that neither of these is marked fixUpperEdge (since in the worst
            * case it might splice one of these edges into tess->event, and
            * violate the invariant that fixable edges are the only right-going
            * edge from their associated vertex).
            */
            if( Sweep.checkForIntersect( tess, regUp )) {
              /* WalkDirtyRegions() was called recursively; we're done */
              return;
            }
          } else {
            /* Even though we can't use CheckForIntersect(), the Org vertices
            * may violate the dictionary edge ordering.  Check and correct this.
            */
            Sweep.checkForRightSplice( tess, regUp );
          }
        }
        if( eUp.Org === eLo.Org && eUp.Dst === eLo.Dst ) {
          /* A degenerate loop consisting of only two edges -- delete it. */
          Sweep.addWinding( eLo, eUp );
          Sweep.deleteRegion( tess, regUp );
          tess.mesh.delete( eUp );
          regUp = Sweep.regionAbove( regLo );
        }
      }
    }
  
  
    //static void ConnectRightVertex( TESStesselator *tess, ActiveRegion *regUp, TESShalfEdge *eBottomLeft )
    Sweep.connectRightVertex = function( tess, regUp, eBottomLeft ) {
      /*
      * Purpose: connect a "right" vertex vEvent (one where all edges go left)
      * to the unprocessed portion of the mesh.  Since there are no right-going
      * edges, two regions (one above vEvent and one below) are being merged
      * into one.  "regUp" is the upper of these two regions.
      *
      * There are two reasons for doing this (adding a right-going edge):
      *  - if the two regions being merged are "inside", we must add an edge
      *    to keep them separated (the combined region would not be monotone).
      *  - in any case, we must leave some record of vEvent in the dictionary,
      *    so that we can merge vEvent with features that we have not seen yet.
      *    For example, maybe there is a vertical edge which passes just to
      *    the right of vEvent; we would like to splice vEvent into this edge.
      *
      * However, we don't want to connect vEvent to just any vertex.  We don''t
      * want the new edge to cross any other edges; otherwise we will create
      * intersection vertices even when the input data had no self-intersections.
      * (This is a bad thing; if the user's input data has no intersections,
      * we don't want to generate any false intersections ourselves.)
      *
      * Our eventual goal is to connect vEvent to the leftmost unprocessed
      * vertex of the combined region (the union of regUp and regLo).
      * But because of unseen vertices with all right-going edges, and also
      * new vertices which may be created by edge intersections, we don''t
      * know where that leftmost unprocessed vertex is.  In the meantime, we
      * connect vEvent to the closest vertex of either chain, and mark the region
      * as "fixUpperEdge".  This flag says to delete and reconnect this edge
      * to the next processed vertex on the boundary of the combined region.
      * Quite possibly the vertex we connected to will turn out to be the
      * closest one, in which case we won''t need to make any changes.
      */
      var eNew;
      var eTopLeft = eBottomLeft.Onext;
      var regLo = Sweep.regionBelow(regUp);
      var eUp = regUp.eUp;
      var eLo = regLo.eUp;
      var degenerate = false;
  
      if( eUp.Dst !== eLo.Dst ) {
        Sweep.checkForIntersect( tess, regUp );
      }
  
      /* Possible new degeneracies: upper or lower edge of regUp may pass
      * through vEvent, or may coincide with new intersection vertex
      */
      if( Geom.vertEq( eUp.Org, tess.event )) {
        tess.mesh.splice( eTopLeft.Oprev, eUp );
        regUp = Sweep.topLeftRegion( tess, regUp );
        eTopLeft = Sweep.regionBelow( regUp ).eUp;
        Sweep.finishLeftRegions( tess, Sweep.regionBelow(regUp), regLo );
        degenerate = true;
      }
      if( Geom.vertEq( eLo.Org, tess.event )) {
        tess.mesh.splice( eBottomLeft, eLo.Oprev );
        eBottomLeft = Sweep.finishLeftRegions( tess, regLo, null );
        degenerate = true;
      }
      if( degenerate ) {
        Sweep.addRightEdges( tess, regUp, eBottomLeft.Onext, eTopLeft, eTopLeft, true );
        return;
      }
  
      /* Non-degenerate situation -- need to add a temporary, fixable edge.
      * Connect to the closer of eLo->Org, eUp->Org.
      */
      if( Geom.vertLeq( eLo.Org, eUp.Org )) {
        eNew = eLo.Oprev;
      } else {
        eNew = eUp;
      }
      eNew = tess.mesh.connect( eBottomLeft.Lprev, eNew );
  
      /* Prevent cleanup, otherwise eNew might disappear before we've even
      * had a chance to mark it as a temporary edge.
      */
      Sweep.addRightEdges( tess, regUp, eNew, eNew.Onext, eNew.Onext, false );
      eNew.Sym.activeRegion.fixUpperEdge = true;
      Sweep.walkDirtyRegions( tess, regUp );
    }
  
    /* Because vertices at exactly the same location are merged together
    * before we process the sweep event, some degenerate cases can't occur.
    * However if someone eventually makes the modifications required to
    * merge features which are close together, the cases below marked
    * TOLERANCE_NONZERO will be useful.  They were debugged before the
    * code to merge identical vertices in the main loop was added.
    */
    //#define TOLERANCE_NONZERO	FALSE
  
    //static void ConnectLeftDegenerate( TESStesselator *tess, ActiveRegion *regUp, TESSvertex *vEvent )
    Sweep.connectLeftDegenerate = function( tess, regUp, vEvent ) {
      /*
      * The event vertex lies exacty on an already-processed edge or vertex.
      * Adding the new vertex involves splicing it into the already-processed
      * part of the mesh.
      */
      var e, eTopLeft, eTopRight, eLast;
      var reg;
  
      e = regUp.eUp;
      if( Geom.vertEq( e.Org, vEvent )) {
        /* e->Org is an unprocessed vertex - just combine them, and wait
        * for e->Org to be pulled from the queue
        */
        assert( false /*TOLERANCE_NONZERO*/ );
        Sweep.spliceMergeVertices( tess, e, vEvent.anEdge );
        return;
      }
  
      if( ! Geom.vertEq( e.Dst, vEvent )) {
        /* General case -- splice vEvent into edge e which passes through it */
        tess.mesh.splitEdge( e.Sym );
        if( regUp.fixUpperEdge ) {
          /* This edge was fixable -- delete unused portion of original edge */
          tess.mesh.delete( e.Onext );
          regUp.fixUpperEdge = false;
        }
        tess.mesh.splice( vEvent.anEdge, e );
        Sweep.sweepEvent( tess, vEvent );	/* recurse */
        return;
      }
  
      /* vEvent coincides with e->Dst, which has already been processed.
      * Splice in the additional right-going edges.
      */
      assert( false /*TOLERANCE_NONZERO*/ );
      regUp = Sweep.topRightRegion( regUp );
      reg = Sweep.regionBelow( regUp );
      eTopRight = reg.eUp.Sym;
      eTopLeft = eLast = eTopRight.Onext;
      if( reg.fixUpperEdge ) {
        /* Here e->Dst has only a single fixable edge going right.
        * We can delete it since now we have some real right-going edges.
        */
        assert( eTopLeft !== eTopRight );   /* there are some left edges too */
        Sweep.deleteRegion( tess, reg );
        tess.mesh.delete( eTopRight );
        eTopRight = eTopLeft.Oprev;
      }
      tess.mesh.splice( vEvent.anEdge, eTopRight );
      if( ! Geom.edgeGoesLeft( eTopLeft )) {
        /* e->Dst had no left-going edges -- indicate this to AddRightEdges() */
        eTopLeft = null;
      }
      Sweep.addRightEdges( tess, regUp, eTopRight.Onext, eLast, eTopLeft, true );
    }
  
  
    //static void ConnectLeftVertex( TESStesselator *tess, TESSvertex *vEvent )
    Sweep.connectLeftVertex = function( tess, vEvent ) {
      /*
      * Purpose: connect a "left" vertex (one where both edges go right)
      * to the processed portion of the mesh.  Let R be the active region
      * containing vEvent, and let U and L be the upper and lower edge
      * chains of R.  There are two possibilities:
      *
      * - the normal case: split R into two regions, by connecting vEvent to
      *   the rightmost vertex of U or L lying to the left of the sweep line
      *
      * - the degenerate case: if vEvent is close enough to U or L, we
      *   merge vEvent into that edge chain.  The subcases are:
      *	- merging with the rightmost vertex of U or L
      *	- merging with the active edge of U or L
      *	- merging with an already-processed portion of U or L
      */
      var regUp, regLo, reg;
      var eUp, eLo, eNew;
      var tmp = new ActiveRegion();
  
      /* assert( vEvent->anEdge->Onext->Onext == vEvent->anEdge ); */
  
      /* Get a pointer to the active region containing vEvent */
      tmp.eUp = vEvent.anEdge.Sym;
      /* __GL_DICTLISTKEY */ /* tessDictListSearch */
      regUp = tess.dict.search( tmp ).key;
      regLo = Sweep.regionBelow( regUp );
      if( !regLo ) {
        // This may happen if the input polygon is coplanar.
        return;
      }
      eUp = regUp.eUp;
      eLo = regLo.eUp;
  
      /* Try merging with U or L first */
      if( Geom.edgeSign( eUp.Dst, vEvent, eUp.Org ) === 0.0 ) {
        Sweep.connectLeftDegenerate( tess, regUp, vEvent );
        return;
      }
  
      /* Connect vEvent to rightmost processed vertex of either chain.
      * e->Dst is the vertex that we will connect to vEvent.
      */
      reg = Geom.vertLeq( eLo.Dst, eUp.Dst ) ? regUp : regLo;
  
      if( regUp.inside || reg.fixUpperEdge) {
        if( reg === regUp ) {
          eNew = tess.mesh.connect( vEvent.anEdge.Sym, eUp.Lnext );
        } else {
          var tempHalfEdge = tess.mesh.connect( eLo.Dnext, vEvent.anEdge);
          eNew = tempHalfEdge.Sym;
        }
        if( reg.fixUpperEdge ) {
          Sweep.fixUpperEdge( tess, reg, eNew );
        } else {
          Sweep.computeWinding( tess, Sweep.addRegionBelow( tess, regUp, eNew ));
        }
        Sweep.sweepEvent( tess, vEvent );
      } else {
        /* The new vertex is in a region which does not belong to the polygon.
        * We don''t need to connect this vertex to the rest of the mesh.
        */
        Sweep.addRightEdges( tess, regUp, vEvent.anEdge, vEvent.anEdge, null, true );
      }
    };
  
  
    //static void SweepEvent( TESStesselator *tess, TESSvertex *vEvent )
    Sweep.sweepEvent = function( tess, vEvent ) {
      /*
      * Does everything necessary when the sweep line crosses a vertex.
      * Updates the mesh and the edge dictionary.
      */
  
      tess.event = vEvent;		/* for access in EdgeLeq() */
      Sweep.debugEvent( tess );
  
      /* Check if this vertex is the right endpoint of an edge that is
      * already in the dictionary.  In this case we don't need to waste
      * time searching for the location to insert new edges.
      */
      var e = vEvent.anEdge;
      while( e.activeRegion === null ) {
        e = e.Onext;
        if( e == vEvent.anEdge ) {
          /* All edges go right -- not incident to any processed edges */
          Sweep.connectLeftVertex( tess, vEvent );
          return;
        }
      }
  
      /* Processing consists of two phases: first we "finish" all the
      * active regions where both the upper and lower edges terminate
      * at vEvent (ie. vEvent is closing off these regions).
      * We mark these faces "inside" or "outside" the polygon according
      * to their winding number, and delete the edges from the dictionary.
      * This takes care of all the left-going edges from vEvent.
      */
      var regUp = Sweep.topLeftRegion( tess, e.activeRegion );
      assert( regUp !== null );
    //	if (regUp == NULL) longjmp(tess->env,1);
      var reg = Sweep.regionBelow( regUp );
      var eTopLeft = reg.eUp;
      var eBottomLeft = Sweep.finishLeftRegions( tess, reg, null );
  
      /* Next we process all the right-going edges from vEvent.  This
      * involves adding the edges to the dictionary, and creating the
      * associated "active regions" which record information about the
      * regions between adjacent dictionary edges.
      */
      if( eBottomLeft.Onext === eTopLeft ) {
        /* No right-going edges -- add a temporary "fixable" edge */
        Sweep.connectRightVertex( tess, regUp, eBottomLeft );
      } else {
        Sweep.addRightEdges( tess, regUp, eBottomLeft.Onext, eTopLeft, eTopLeft, true );
      }
    };
  
  
    /* Make the sentinel coordinates big enough that they will never be
    * merged with real input features.
    */
  
    //static void AddSentinel( TESStesselator *tess, TESSreal smin, TESSreal smax, TESSreal t )
    Sweep.addSentinel = function( tess, smin, smax, t ) {
      /*
      * We add two sentinel edges above and below all other edges,
      * to avoid special cases at the top and bottom.
      */
      var reg = new ActiveRegion();
      var e = tess.mesh.makeEdge();
    //	if (e == NULL) longjmp(tess->env,1);
  
      e.Org.s = smax;
      e.Org.t = t;
      e.Dst.s = smin;
      e.Dst.t = t;
      tess.event = e.Dst;		/* initialize it */
  
      reg.eUp = e;
      reg.windingNumber = 0;
      reg.inside = false;
      reg.fixUpperEdge = false;
      reg.sentinel = true;
      reg.dirty = false;
      reg.nodeUp = tess.dict.insert( reg );
    //	if (reg->nodeUp == NULL) longjmp(tess->env,1);
    }
  
  
    //static void InitEdgeDict( TESStesselator *tess )
    Sweep.initEdgeDict = function( tess ) {
      /*
      * We maintain an ordering of edge intersections with the sweep line.
      * This order is maintained in a dynamic dictionary.
      */
      tess.dict = new Dict( tess, Sweep.edgeLeq );
    //	if (tess->dict == NULL) longjmp(tess->env,1);
  
      var w = (tess.bmax[0] - tess.bmin[0]);
      var h = (tess.bmax[1] - tess.bmin[1]);
  
      var smin = tess.bmin[0] - w;
      var smax = tess.bmax[0] + w;
      var tmin = tess.bmin[1] - h;
      var tmax = tess.bmax[1] + h;
  
      Sweep.addSentinel( tess, smin, smax, tmin );
      Sweep.addSentinel( tess, smin, smax, tmax );
    }
  
  
    Sweep.doneEdgeDict = function( tess )
    {
      var reg;
      var fixedEdges = 0;
  
      while( (reg = tess.dict.min().key) !== null ) {
        /*
        * At the end of all processing, the dictionary should contain
        * only the two sentinel edges, plus at most one "fixable" edge
        * created by ConnectRightVertex().
        */
        if( ! reg.sentinel ) {
          assert( reg.fixUpperEdge );
          assert( ++fixedEdges == 1 );
        }
        assert( reg.windingNumber == 0 );
        Sweep.deleteRegion( tess, reg );
        /*    tessMeshDelete( reg->eUp );*/
      }
    //	dictDeleteDict( &tess->alloc, tess->dict );
    }
  
  
    Sweep.removeDegenerateEdges = function( tess ) {
      /*
      * Remove zero-length edges, and contours with fewer than 3 vertices.
      */
      var e, eNext, eLnext;
      var eHead = tess.mesh.eHead;
  
      /*LINTED*/
      for( e = eHead.next; e !== eHead; e = eNext ) {
        eNext = e.next;
        eLnext = e.Lnext;
  
        if( Geom.vertEq( e.Org, e.Dst ) && e.Lnext.Lnext !== e ) {
          /* Zero-length edge, contour has at least 3 edges */
          Sweep.spliceMergeVertices( tess, eLnext, e );	/* deletes e->Org */
          tess.mesh.delete( e ); /* e is a self-loop */
          e = eLnext;
          eLnext = e.Lnext;
        }
        if( eLnext.Lnext === e ) {
          /* Degenerate contour (one or two edges) */
          if( eLnext !== e ) {
            if( eLnext === eNext || eLnext === eNext.Sym ) { eNext = eNext.next; }
            tess.mesh.delete( eLnext );
          }
          if( e === eNext || e === eNext.Sym ) { eNext = eNext.next; }
          tess.mesh.delete( e );
        }
      }
    }
  
    Sweep.initPriorityQ = function( tess ) {
      /*
      * Insert all vertices into the priority queue which determines the
      * order in which vertices cross the sweep line.
      */
      var pq;
      var v, vHead;
      var vertexCount = 0;
      
      vHead = tess.mesh.vHead;
      for( v = vHead.next; v !== vHead; v = v.next ) {
        vertexCount++;
      }
      /* Make sure there is enough space for sentinels. */
      vertexCount += 8; //MAX( 8, tess->alloc.extraVertices );
      
      pq = tess.pq = new PriorityQ( vertexCount, Geom.vertLeq );
    //	if (pq == NULL) return 0;
  
      vHead = tess.mesh.vHead;
      for( v = vHead.next; v !== vHead; v = v.next ) {
        v.pqHandle = pq.insert( v );
    //		if (v.pqHandle == INV_HANDLE)
    //			break;
      }
  
      if (v !== vHead) {
        return false;
      }
  
      pq.init();
  
      return true;
    }
  
  
    Sweep.donePriorityQ = function( tess ) {
      tess.pq = null;
    }
  
  
    Sweep.removeDegenerateFaces = function( tess, mesh ) {
      /*
      * Delete any degenerate faces with only two edges.  WalkDirtyRegions()
      * will catch almost all of these, but it won't catch degenerate faces
      * produced by splice operations on already-processed edges.
      * The two places this can happen are in FinishLeftRegions(), when
      * we splice in a "temporary" edge produced by ConnectRightVertex(),
      * and in CheckForLeftSplice(), where we splice already-processed
      * edges to ensure that our dictionary invariants are not violated
      * by numerical errors.
      *
      * In both these cases it is *very* dangerous to delete the offending
      * edge at the time, since one of the routines further up the stack
      * will sometimes be keeping a pointer to that edge.
      */
      var f, fNext;
      var e;
  
      /*LINTED*/
      for( f = mesh.fHead.next; f !== mesh.fHead; f = fNext ) {
        fNext = f.next;
        e = f.anEdge;
        assert( e.Lnext !== e );
  
        if( e.Lnext.Lnext === e ) {
          /* A face with only two edges */
          Sweep.addWinding( e.Onext, e );
          tess.mesh.delete( e );
        }
      }
      return true;
    }
  
    Sweep.computeInterior = function( tess ) {
      /*
      * tessComputeInterior( tess ) computes the planar arrangement specified
      * by the given contours, and further subdivides this arrangement
      * into regions.  Each region is marked "inside" if it belongs
      * to the polygon, according to the rule given by tess->windingRule.
      * Each interior region is guaranteed be monotone.
      */
      var v, vNext;
  
      /* Each vertex defines an event for our sweep line.  Start by inserting
      * all the vertices in a priority queue.  Events are processed in
      * lexicographic order, ie.
      *
      *	e1 < e2  iff  e1.x < e2.x || (e1.x == e2.x && e1.y < e2.y)
      */
      Sweep.removeDegenerateEdges( tess );
      if ( !Sweep.initPriorityQ( tess ) ) return false; /* if error */
      Sweep.initEdgeDict( tess );
  
      while( (v = tess.pq.extractMin()) !== null ) {
        for( ;; ) {
          vNext = tess.pq.min();
          if( vNext === null || ! Geom.vertEq( vNext, v )) break;
  
          /* Merge together all vertices at exactly the same location.
          * This is more efficient than processing them one at a time,
          * simplifies the code (see ConnectLeftDegenerate), and is also
          * important for correct handling of certain degenerate cases.
          * For example, suppose there are two identical edges A and B
          * that belong to different contours (so without this code they would
          * be processed by separate sweep events).  Suppose another edge C
          * crosses A and B from above.  When A is processed, we split it
          * at its intersection point with C.  However this also splits C,
          * so when we insert B we may compute a slightly different
          * intersection point.  This might leave two edges with a small
          * gap between them.  This kind of error is especially obvious
          * when using boundary extraction (TESS_BOUNDARY_ONLY).
          */
          vNext = tess.pq.extractMin();
          Sweep.spliceMergeVertices( tess, v.anEdge, vNext.anEdge );
        }
        Sweep.sweepEvent( tess, v );
      }
  
      /* Set tess->event for debugging purposes */
      tess.event = tess.dict.min().key.eUp.Org;
      Sweep.debugEvent( tess );
      Sweep.doneEdgeDict( tess );
      Sweep.donePriorityQ( tess );
  
      if ( !Sweep.removeDegenerateFaces( tess, tess.mesh ) ) return false;
      tess.mesh.check();
  
      return true;
    }
  
  
    function Tesselator() {
  
      /*** state needed for collecting the input data ***/
      this.mesh = null;		/* stores the input contours, and eventually
                the tessellation itself */
  
      /*** state needed for projecting onto the sweep plane ***/
  
      this.normal = [0.0, 0.0, 0.0];	/* user-specified normal (if provided) */
      this.sUnit = [0.0, 0.0, 0.0];	/* unit vector in s-direction (debugging) */
      this.tUnit = [0.0, 0.0, 0.0];	/* unit vector in t-direction (debugging) */
  
      this.bmin = [0.0, 0.0];
      this.bmax = [0.0, 0.0];
  
      /*** state needed for the line sweep ***/
      this.windingRule = Tess2.WINDING_ODD;	/* rule for determining polygon interior */
  
      this.dict = null;		/* edge dictionary for sweep line */
      this.pq = null;		/* priority queue of vertex events */
      this.event = null;		/* current sweep event being processed */
  
      this.vertexIndexCounter = 0;
      
      this.vertices = [];
      this.vertexIndices = [];
      this.vertexCount = 0;
      this.elements = [];
      this.elementCount = 0;
    };
  
    Tesselator.prototype = {
  
      dot_: function(u, v) {
        return (u[0]*v[0] + u[1]*v[1] + u[2]*v[2]);
      },
  
      normalize_: function( v ) {
        var len = v[0]*v[0] + v[1]*v[1] + v[2]*v[2];
        assert( len > 0.0 );
        len = Math.sqrt( len );
        v[0] /= len;
        v[1] /= len;
        v[2] /= len;
      },
  
      longAxis_: function( v ) {
        var i = 0;
        if( Math.abs(v[1]) > Math.abs(v[0]) ) { i = 1; }
        if( Math.abs(v[2]) > Math.abs(v[i]) ) { i = 2; }
        return i;
      },
  
      computeNormal_: function( norm )
      {
        var v, v1, v2;
        var c, tLen2, maxLen2;
        var maxVal = [0,0,0], minVal = [0,0,0], d1 = [0,0,0], d2 = [0,0,0], tNorm = [0,0,0];
        var maxVert = [null,null,null], minVert = [null,null,null];
        var vHead = this.mesh.vHead;
        var i;
  
        v = vHead.next;
        for( i = 0; i < 3; ++i ) {
          c = v.coords[i];
          minVal[i] = c;
          minVert[i] = v;
          maxVal[i] = c;
          maxVert[i] = v;
        }
  
        for( v = vHead.next; v !== vHead; v = v.next ) {
          for( i = 0; i < 3; ++i ) {
            c = v.coords[i];
            if( c < minVal[i] ) { minVal[i] = c; minVert[i] = v; }
            if( c > maxVal[i] ) { maxVal[i] = c; maxVert[i] = v; }
          }
        }
  
        /* Find two vertices separated by at least 1/sqrt(3) of the maximum
        * distance between any two vertices
        */
        i = 0;
        if( maxVal[1] - minVal[1] > maxVal[0] - minVal[0] ) { i = 1; }
        if( maxVal[2] - minVal[2] > maxVal[i] - minVal[i] ) { i = 2; }
        if( minVal[i] >= maxVal[i] ) {
          /* All vertices are the same -- normal doesn't matter */
          norm[0] = 0; norm[1] = 0; norm[2] = 1;
          return;
        }
  
        /* Look for a third vertex which forms the triangle with maximum area
        * (Length of normal == twice the triangle area)
        */
        maxLen2 = 0;
        v1 = minVert[i];
        v2 = maxVert[i];
        d1[0] = v1.coords[0] - v2.coords[0];
        d1[1] = v1.coords[1] - v2.coords[1];
        d1[2] = v1.coords[2] - v2.coords[2];
        for( v = vHead.next; v !== vHead; v = v.next ) {
          d2[0] = v.coords[0] - v2.coords[0];
          d2[1] = v.coords[1] - v2.coords[1];
          d2[2] = v.coords[2] - v2.coords[2];
          tNorm[0] = d1[1]*d2[2] - d1[2]*d2[1];
          tNorm[1] = d1[2]*d2[0] - d1[0]*d2[2];
          tNorm[2] = d1[0]*d2[1] - d1[1]*d2[0];
          tLen2 = tNorm[0]*tNorm[0] + tNorm[1]*tNorm[1] + tNorm[2]*tNorm[2];
          if( tLen2 > maxLen2 ) {
            maxLen2 = tLen2;
            norm[0] = tNorm[0];
            norm[1] = tNorm[1];
            norm[2] = tNorm[2];
          }
        }
  
        if( maxLen2 <= 0 ) {
          /* All points lie on a single line -- any decent normal will do */
          norm[0] = norm[1] = norm[2] = 0;
          norm[this.longAxis_(d1)] = 1;
        }
      },
  
      checkOrientation_: function() {
        var area;
        var f, fHead = this.mesh.fHead;
        var v, vHead = this.mesh.vHead;
        var e;
  
        /* When we compute the normal automatically, we choose the orientation
        * so that the the sum of the signed areas of all contours is non-negative.
        */
        area = 0;
        for( f = fHead.next; f !== fHead; f = f.next ) {
          e = f.anEdge;
          if( e.winding <= 0 ) continue;
          do {
            area += (e.Org.s - e.Dst.s) * (e.Org.t + e.Dst.t);
            e = e.Lnext;
          } while( e !== f.anEdge );
        }
        if( area < 0 ) {
          /* Reverse the orientation by flipping all the t-coordinates */
          for( v = vHead.next; v !== vHead; v = v.next ) {
            v.t = - v.t;
          }
          this.tUnit[0] = - this.tUnit[0];
          this.tUnit[1] = - this.tUnit[1];
          this.tUnit[2] = - this.tUnit[2];
        }
      },
  
    /*	#ifdef FOR_TRITE_TEST_PROGRAM
      #include <stdlib.h>
      extern int RandomSweep;
      #define S_UNIT_X	(RandomSweep ? (2*drand48()-1) : 1.0)
      #define S_UNIT_Y	(RandomSweep ? (2*drand48()-1) : 0.0)
      #else
      #if defined(SLANTED_SWEEP) */
      /* The "feature merging" is not intended to be complete.  There are
      * special cases where edges are nearly parallel to the sweep line
      * which are not implemented.  The algorithm should still behave
      * robustly (ie. produce a reasonable tesselation) in the presence
      * of such edges, however it may miss features which could have been
      * merged.  We could minimize this effect by choosing the sweep line
      * direction to be something unusual (ie. not parallel to one of the
      * coordinate axes).
      */
    /*	#define S_UNIT_X	(TESSreal)0.50941539564955385	// Pre-normalized
      #define S_UNIT_Y	(TESSreal)0.86052074622010633
      #else
      #define S_UNIT_X	(TESSreal)1.0
      #define S_UNIT_Y	(TESSreal)0.0
      #endif
      #endif*/
  
      /* Determine the polygon normal and project vertices onto the plane
      * of the polygon.
      */
      projectPolygon_: function() {
        var v, vHead = this.mesh.vHead;
        var norm = [0,0,0];
        var sUnit, tUnit;
        var i, first, computedNormal = false;
  
        norm[0] = this.normal[0];
        norm[1] = this.normal[1];
        norm[2] = this.normal[2];
        if( norm[0] === 0.0 && norm[1] === 0.0 && norm[2] === 0.0 ) {
          this.computeNormal_( norm );
          computedNormal = true;
        }
        sUnit = this.sUnit;
        tUnit = this.tUnit;
        i = this.longAxis_( norm );
  
    /*	#if defined(FOR_TRITE_TEST_PROGRAM) || defined(TRUE_PROJECT)
        // Choose the initial sUnit vector to be approximately perpendicular
        // to the normal.
        
        Normalize( norm );
  
        sUnit[i] = 0;
        sUnit[(i+1)%3] = S_UNIT_X;
        sUnit[(i+2)%3] = S_UNIT_Y;
  
        // Now make it exactly perpendicular 
        w = Dot( sUnit, norm );
        sUnit[0] -= w * norm[0];
        sUnit[1] -= w * norm[1];
        sUnit[2] -= w * norm[2];
        Normalize( sUnit );
  
        // Choose tUnit so that (sUnit,tUnit,norm) form a right-handed frame 
        tUnit[0] = norm[1]*sUnit[2] - norm[2]*sUnit[1];
        tUnit[1] = norm[2]*sUnit[0] - norm[0]*sUnit[2];
        tUnit[2] = norm[0]*sUnit[1] - norm[1]*sUnit[0];
        Normalize( tUnit );
      #else*/
        /* Project perpendicular to a coordinate axis -- better numerically */
        sUnit[i] = 0;
        sUnit[(i+1)%3] = 1.0;
        sUnit[(i+2)%3] = 0.0;
  
        tUnit[i] = 0;
        tUnit[(i+1)%3] = 0.0;
        tUnit[(i+2)%3] = (norm[i] > 0) ? 1.0 : -1.0;
    //	#endif
  
        /* Project the vertices onto the sweep plane */
        for( v = vHead.next; v !== vHead; v = v.next ) {
          v.s = this.dot_( v.coords, sUnit );
          v.t = this.dot_( v.coords, tUnit );
        }
        if( computedNormal ) {
          this.checkOrientation_();
        }
  
        /* Compute ST bounds. */
        first = true;
        for( v = vHead.next; v !== vHead; v = v.next ) {
          if (first) {
            this.bmin[0] = this.bmax[0] = v.s;
            this.bmin[1] = this.bmax[1] = v.t;
            first = false;
          } else {
            if (v.s < this.bmin[0]) this.bmin[0] = v.s;
            if (v.s > this.bmax[0]) this.bmax[0] = v.s;
            if (v.t < this.bmin[1]) this.bmin[1] = v.t;
            if (v.t > this.bmax[1]) this.bmax[1] = v.t;
          }
        }
      },
  
      addWinding_: function(eDst,eSrc) {
        eDst.winding += eSrc.winding;
        eDst.Sym.winding += eSrc.Sym.winding;
      },
      
      /* tessMeshTessellateMonoRegion( face ) tessellates a monotone region
      * (what else would it do??)  The region must consist of a single
      * loop of half-edges (see mesh.h) oriented CCW.  "Monotone" in this
      * case means that any vertical line intersects the interior of the
      * region in a single interval.  
      *
      * Tessellation consists of adding interior edges (actually pairs of
      * half-edges), to split the region into non-overlapping triangles.
      *
      * The basic idea is explained in Preparata and Shamos (which I don''t
      * have handy right now), although their implementation is more
      * complicated than this one.  The are two edge chains, an upper chain
      * and a lower chain.  We process all vertices from both chains in order,
      * from right to left.
      *
      * The algorithm ensures that the following invariant holds after each
      * vertex is processed: the untessellated region consists of two
      * chains, where one chain (say the upper) is a single edge, and
      * the other chain is concave.  The left vertex of the single edge
      * is always to the left of all vertices in the concave chain.
      *
      * Each step consists of adding the rightmost unprocessed vertex to one
      * of the two chains, and forming a fan of triangles from the rightmost
      * of two chain endpoints.  Determining whether we can add each triangle
      * to the fan is a simple orientation test.  By making the fan as large
      * as possible, we restore the invariant (check it yourself).
      */
    //	int tessMeshTessellateMonoRegion( TESSmesh *mesh, TESSface *face )
      tessellateMonoRegion_: function( mesh, face ) {
        var up, lo;
  
        /* All edges are oriented CCW around the boundary of the region.
        * First, find the half-edge whose origin vertex is rightmost.
        * Since the sweep goes from left to right, face->anEdge should
        * be close to the edge we want.
        */
        up = face.anEdge;
        assert( up.Lnext !== up && up.Lnext.Lnext !== up );
  
        for( ; Geom.vertLeq( up.Dst, up.Org ); up = up.Lprev )
          ;
        for( ; Geom.vertLeq( up.Org, up.Dst ); up = up.Lnext )
          ;
        lo = up.Lprev;
  
        while( up.Lnext !== lo ) {
          if( Geom.vertLeq( up.Dst, lo.Org )) {
            /* up->Dst is on the left.  It is safe to form triangles from lo->Org.
            * The EdgeGoesLeft test guarantees progress even when some triangles
            * are CW, given that the upper and lower chains are truly monotone.
            */
            while( lo.Lnext !== up && (Geom.edgeGoesLeft( lo.Lnext )
              || Geom.edgeSign( lo.Org, lo.Dst, lo.Lnext.Dst ) <= 0.0 )) {
                var tempHalfEdge = mesh.connect( lo.Lnext, lo );
                //if (tempHalfEdge == NULL) return 0;
                lo = tempHalfEdge.Sym;
            }
            lo = lo.Lprev;
          } else {
            /* lo->Org is on the left.  We can make CCW triangles from up->Dst. */
            while( lo.Lnext != up && (Geom.edgeGoesRight( up.Lprev )
              || Geom.edgeSign( up.Dst, up.Org, up.Lprev.Org ) >= 0.0 )) {
                var tempHalfEdge = mesh.connect( up, up.Lprev );
                //if (tempHalfEdge == NULL) return 0;
                up = tempHalfEdge.Sym;
            }
            up = up.Lnext;
          }
        }
  
        /* Now lo->Org == up->Dst == the leftmost vertex.  The remaining region
        * can be tessellated in a fan from this leftmost vertex.
        */
        assert( lo.Lnext !== up );
        while( lo.Lnext.Lnext !== up ) {
          var tempHalfEdge = mesh.connect( lo.Lnext, lo );
          //if (tempHalfEdge == NULL) return 0;
          lo = tempHalfEdge.Sym;
        }
  
        return true;
      },
  
  
      /* tessMeshTessellateInterior( mesh ) tessellates each region of
      * the mesh which is marked "inside" the polygon.  Each such region
      * must be monotone.
      */
      //int tessMeshTessellateInterior( TESSmesh *mesh )
      tessellateInterior_: function( mesh ) {
        var f, next;
  
        /*LINTED*/
        for( f = mesh.fHead.next; f !== mesh.fHead; f = next ) {
          /* Make sure we don''t try to tessellate the new triangles. */
          next = f.next;
          if( f.inside ) {
            if ( !this.tessellateMonoRegion_( mesh, f ) ) return false;
          }
        }
  
        return true;
      },
  
  
      /* tessMeshDiscardExterior( mesh ) zaps (ie. sets to NULL) all faces
      * which are not marked "inside" the polygon.  Since further mesh operations
      * on NULL faces are not allowed, the main purpose is to clean up the
      * mesh so that exterior loops are not represented in the data structure.
      */
      //void tessMeshDiscardExterior( TESSmesh *mesh )
      discardExterior_: function( mesh ) {
        var f, next;
  
        /*LINTED*/
        for( f = mesh.fHead.next; f !== mesh.fHead; f = next ) {
          /* Since f will be destroyed, save its next pointer. */
          next = f.next;
          if( ! f.inside ) {
            mesh.zapFace( f );
          }
        }
      },
  
      /* tessMeshSetWindingNumber( mesh, value, keepOnlyBoundary ) resets the
      * winding numbers on all edges so that regions marked "inside" the
      * polygon have a winding number of "value", and regions outside
      * have a winding number of 0.
      *
      * If keepOnlyBoundary is TRUE, it also deletes all edges which do not
      * separate an interior region from an exterior one.
      */
    //	int tessMeshSetWindingNumber( TESSmesh *mesh, int value, int keepOnlyBoundary )
      setWindingNumber_: function( mesh, value, keepOnlyBoundary ) {
        var e, eNext;
  
        for( e = mesh.eHead.next; e !== mesh.eHead; e = eNext ) {
          eNext = e.next;
          if( e.Rface.inside !== e.Lface.inside ) {
  
            /* This is a boundary edge (one side is interior, one is exterior). */
            e.winding = (e.Lface.inside) ? value : -value;
          } else {
  
            /* Both regions are interior, or both are exterior. */
            if( ! keepOnlyBoundary ) {
              e.winding = 0;
            } else {
              mesh.delete( e );
            }
          }
        }
      },
  
      getNeighbourFace_: function(edge)
      {
        if (!edge.Rface)
          return -1;
        if (!edge.Rface.inside)
          return -1;
        return edge.Rface.n;
      },
  
      outputPolymesh_: function( mesh, elementType, polySize, vertexSize ) {
        var v;
        var f;
        var edge;
        var maxFaceCount = 0;
        var maxVertexCount = 0;
        var faceVerts, i;
        var elements = 0;
        var vert;
  
        // Assume that the input data is triangles now.
        // Try to merge as many polygons as possible
        if (polySize > 3)
        {
          mesh.mergeConvexFaces( polySize );
        }
  
        // Mark unused
        for ( v = mesh.vHead.next; v !== mesh.vHead; v = v.next )
          v.n = -1;
  
        // Create unique IDs for all vertices and faces.
        for ( f = mesh.fHead.next; f != mesh.fHead; f = f.next )
        {
          f.n = -1;
          if( !f.inside ) continue;
  
          edge = f.anEdge;
          faceVerts = 0;
          do
          {
            v = edge.Org;
            if ( v.n === -1 )
            {
              v.n = maxVertexCount;
              maxVertexCount++;
            }
            faceVerts++;
            edge = edge.Lnext;
          }
          while (edge !== f.anEdge);
          
          assert( faceVerts <= polySize );
  
          f.n = maxFaceCount;
          ++maxFaceCount;
        }
  
        this.elementCount = maxFaceCount;
        if (elementType == Tess2.CONNECTED_POLYGONS)
          maxFaceCount *= 2;
    /*		tess.elements = (TESSindex*)tess->alloc.memalloc( tess->alloc.userData,
                                  sizeof(TESSindex) * maxFaceCount * polySize );
        if (!tess->elements)
        {
          tess->outOfMemory = 1;
          return;
        }*/
        this.elements = [];
        this.elements.length = maxFaceCount * polySize;
        
        this.vertexCount = maxVertexCount;
    /*		tess->vertices = (TESSreal*)tess->alloc.memalloc( tess->alloc.userData,
                                 sizeof(TESSreal) * tess->vertexCount * vertexSize );
        if (!tess->vertices)
        {
          tess->outOfMemory = 1;
          return;
        }*/
        this.vertices = [];
        this.vertices.length = maxVertexCount * vertexSize;
  
    /*		tess->vertexIndices = (TESSindex*)tess->alloc.memalloc( tess->alloc.userData,
                                      sizeof(TESSindex) * tess->vertexCount );
        if (!tess->vertexIndices)
        {
          tess->outOfMemory = 1;
          return;
        }*/
        this.vertexIndices = [];
        this.vertexIndices.length = maxVertexCount;
  
        
        // Output vertices.
        for ( v = mesh.vHead.next; v !== mesh.vHead; v = v.next )
        {
          if ( v.n != -1 )
          {
            // Store coordinate
            var idx = v.n * vertexSize;
            this.vertices[idx+0] = v.coords[0];
            this.vertices[idx+1] = v.coords[1];
            if ( vertexSize > 2 )
              this.vertices[idx+2] = v.coords[2];
            // Store vertex index.
            this.vertexIndices[v.n] = v.idx;
          }
        }
  
        // Output indices.
        var nel = 0;
        for ( f = mesh.fHead.next; f !== mesh.fHead; f = f.next )
        {
          if ( !f.inside ) continue;
          
          // Store polygon
          edge = f.anEdge;
          faceVerts = 0;
          do
          {
            v = edge.Org;
            this.elements[nel++] = v.n;
            faceVerts++;
            edge = edge.Lnext;
          }
          while (edge !== f.anEdge);
          // Fill unused.
          for (i = faceVerts; i < polySize; ++i)
            this.elements[nel++] = -1;
  
          // Store polygon connectivity
          if ( elementType == Tess2.CONNECTED_POLYGONS )
          {
            edge = f.anEdge;
            do
            {
              this.elements[nel++] = this.getNeighbourFace_( edge );
              edge = edge.Lnext;
            }
            while (edge !== f.anEdge);
            // Fill unused.
            for (i = faceVerts; i < polySize; ++i)
              this.elements[nel++] = -1;
          }
        }
      },
  
    //	void OutputContours( TESStesselator *tess, TESSmesh *mesh, int vertexSize )
      outputContours_: function( mesh, vertexSize ) {
        var f;
        var edge;
        var start;
        var verts;
        var elements;
        var vertInds;
        var startVert = 0;
        var vertCount = 0;
  
        this.vertexCount = 0;
        this.elementCount = 0;
  
        for ( f = mesh.fHead.next; f !== mesh.fHead; f = f.next )
        {
          if ( !f.inside ) continue;
  
          start = edge = f.anEdge;
          do
          {
            this.vertexCount++;
            edge = edge.Lnext;
          }
          while ( edge !== start );
  
          this.elementCount++;
        }
  
    /*		tess->elements = (TESSindex*)tess->alloc.memalloc( tess->alloc.userData,
                                  sizeof(TESSindex) * tess->elementCount * 2 );
        if (!tess->elements)
        {
          tess->outOfMemory = 1;
          return;
        }*/
        this.elements = [];
        this.elements.length = this.elementCount * 2;
        
    /*		tess->vertices = (TESSreal*)tess->alloc.memalloc( tess->alloc.userData,
                                  sizeof(TESSreal) * tess->vertexCount * vertexSize );
        if (!tess->vertices)
        {
          tess->outOfMemory = 1;
          return;
        }*/
        this.vertices = [];
        this.vertices.length = this.vertexCount * vertexSize;
  
    /*		tess->vertexIndices = (TESSindex*)tess->alloc.memalloc( tess->alloc.userData,
                                      sizeof(TESSindex) * tess->vertexCount );
        if (!tess->vertexIndices)
        {
          tess->outOfMemory = 1;
          return;
        }*/
        this.vertexIndices = [];
        this.vertexIndices.length = this.vertexCount;
  
        var nv = 0;
        var nvi = 0;
        var nel = 0;
        startVert = 0;
  
        for ( f = mesh.fHead.next; f !== mesh.fHead; f = f.next )
        {
          if ( !f.inside ) continue;
  
          vertCount = 0;
          start = edge = f.anEdge;
          do
          {
            this.vertices[nv++] = edge.Org.coords[0];
            this.vertices[nv++] = edge.Org.coords[1];
            if ( vertexSize > 2 )
              this.vertices[nv++] = edge.Org.coords[2];
            this.vertexIndices[nvi++] = edge.Org.idx;
            vertCount++;
            edge = edge.Lnext;
          }
          while ( edge !== start );
  
          this.elements[nel++] = startVert;
          this.elements[nel++] = vertCount;
  
          startVert += vertCount;
        }
      },
  
      addContour: function( size, vertices )
      {
        var e;
        var i;
  
        if ( this.mesh === null )
            this.mesh = new TESSmesh();
    /*	 	if ( tess->mesh == NULL ) {
          tess->outOfMemory = 1;
          return;
        }*/
  
        if ( size < 2 )
          size = 2;
        if ( size > 3 )
          size = 3;
  
        e = null;
  
        for( i = 0; i < vertices.length; i += size )
        {
          if( e == null ) {
            /* Make a self-loop (one vertex, one edge). */
            e = this.mesh.makeEdge();
    /*				if ( e == NULL ) {
              tess->outOfMemory = 1;
              return;
            }*/
            this.mesh.splice( e, e.Sym );
          } else {
            /* Create a new vertex and edge which immediately follow e
            * in the ordering around the left face.
            */
            this.mesh.splitEdge( e );
            e = e.Lnext;
          }
  
          /* The new vertex is now e->Org. */
          e.Org.coords[0] = vertices[i+0];
          e.Org.coords[1] = vertices[i+1];
          if ( size > 2 )
            e.Org.coords[2] = vertices[i+2];
          else
            e.Org.coords[2] = 0.0;
          /* Store the insertion number so that the vertex can be later recognized. */
          e.Org.idx = this.vertexIndexCounter++;
  
          /* The winding of an edge says how the winding number changes as we
          * cross from the edge''s right face to its left face.  We add the
          * vertices in such an order that a CCW contour will add +1 to
          * the winding number of the region inside the contour.
          */
          e.winding = 1;
          e.Sym.winding = -1;
        }
      },
  
    //	int tessTesselate( TESStesselator *tess, int windingRule, int elementType, int polySize, int vertexSize, const TESSreal* normal )
      tesselate: function( windingRule, elementType, polySize, vertexSize, normal ) {
        this.vertices = [];
        this.elements = [];
        this.vertexIndices = [];
  
        this.vertexIndexCounter = 0;
        
        if (normal)
        {
          this.normal[0] = normal[0];
          this.normal[1] = normal[1];
          this.normal[2] = normal[2];
        }
  
        this.windingRule = windingRule;
  
        if (vertexSize < 2)
          vertexSize = 2;
        if (vertexSize > 3)
          vertexSize = 3;
  
    /*		if (setjmp(tess->env) != 0) { 
          // come back here if out of memory
          return 0;
        }*/
  
        if (!this.mesh)
        {
          return false;
        }
  
        /* Determine the polygon normal and project vertices onto the plane
        * of the polygon.
        */
        this.projectPolygon_();
  
        /* tessComputeInterior( tess ) computes the planar arrangement specified
        * by the given contours, and further subdivides this arrangement
        * into regions.  Each region is marked "inside" if it belongs
        * to the polygon, according to the rule given by tess->windingRule.
        * Each interior region is guaranteed be monotone.
        */
        Sweep.computeInterior( this );
  
        var mesh = this.mesh;
  
        /* If the user wants only the boundary contours, we throw away all edges
        * except those which separate the interior from the exterior.
        * Otherwise we tessellate all the regions marked "inside".
        */
        if (elementType == Tess2.BOUNDARY_CONTOURS) {
          this.setWindingNumber_( mesh, 1, true );
        } else {
          this.tessellateInterior_( mesh ); 
        }
    //		if (rc == 0) longjmp(tess->env,1);  /* could've used a label */
  
        mesh.check();
  
        if (elementType == Tess2.BOUNDARY_CONTOURS) {
          this.outputContours_( mesh, vertexSize );     /* output contours */
        }
        else
        {
          this.outputPolymesh_( mesh, elementType, polySize, vertexSize );     /* output polygons */
        }
  
  //			tess.mesh = null;
  
        return true;
      }
    };